본문 바로가기

알고리즘/백준46

백준 2073 수도배관공사 C++ 간단한 해설 간단하게 문제를 보면 단순히 배낭문제라 생각할 수 있고, 풀이는 다음과 같다. #include #include #include #define ll long longusing namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int d,p; cin>>d>>p; vector> v(p); for(int i=0;i>v[i].first>>v[i].second; // length, capacity } vector> dp(p+1,vector(d+1,0)); // gae, length for(int i=1;i 그러나 문제에서 주어진 메모리는 128MB이므로,이 문제를 2차원 dp로 풀고자.. 2025. 3. 2.
백준 13459 구슬 탈출 C++ 간단한 해설푸는 방식은 구슬 탈출 2와 같다. 백준 134760 구슬 탈출 2 C++간단한 해설  백준 16197 두 동전 C++간단한 해설간단하게 bfs+구현(약간의 시뮬)를 하면 된다. 일단 보드 판을 생성하고, 생성한 보드판을 방문했나? 를 알려면 unorderd_map을 사용하자.unordered_map의ash9river.tistory.com  탈출 여부에 따라 답만 1 or 0을 출력하면 된다. 답#include #include #include #include #include using namespace std;int n,m;int dy[4]={-1,1,0,0};int dx[4]={0,0,-1,1};pair endHole;string boardToString(vector& board){ s.. 2025. 2. 24.
백준 134760 구슬 탈출 2 C++ 간단한 해설  백준 16197 두 동전 C++간단한 해설간단하게 bfs+구현(약간의 시뮬)를 하면 된다. 일단 보드 판을 생성하고, 생성한 보드판을 방문했나? 를 알려면 unorderd_map을 사용하자.unordered_map의 find()를 통하여 O(1) 안에 생성한 보ash9river.tistory.com 이전에 풀었던 두 동전 문제와 유사하게 풀이할 수 있다. 일단 유형은 bfs+구현(시뮬)의 느낌이다. hash맵인 unordered_map을 이용하여 방문 여부를 O(1)의 시간복잡도로 확인하고, 기울여서 구슬을 넣어보면 된다. 기울였을 때, 구슬 2개가 동시에 들어가면 실패인데, 이 테스트 케이스를 잘 확인해봐야 한다. 기울이는 것을 어떻게 구현할까 고민했는데, 경우의 수가 4가지이므로 그냥 .. 2025. 2. 24.
백준 16197 두 동전 C++ 간단한 해설간단하게 bfs+구현(약간의 시뮬)를 하면 된다. 일단 보드 판을 생성하고, 생성한 보드판을 방문했나? 를 알려면 unorderd_map을 사용하자.unordered_map의 find()를 통하여 O(1) 안에 생성한 보드판을 이전에 방문했는지 탐색할 수 있다. 나머지는 그냥 쌩 구현 답 #include #include #include #include #include #include using namespace std;int n,m;vector board;unordered_map visited;pair,pair> dongPosition={{-1,-1},{-1,-1}};int dy[4]={-1,1,0,0};int dx[4]={0,0,-1,1};string boardToString(vector& .. 2025. 2. 24.
백준 10282 해킹 C++ 간단한 해설 단순하게 다익스트라를 하면 된다. (c에서 시작해서, b->a로 이어지는데, s초가 더해진다.)그러나 단순하게 2차원 배열로 그래프를 만들면 25%정도에서 메모리 초과가 발생한다.나는 그래서 연결리스트로 풀 수 있지만 꼼수로 다음과 같이 그래프 연결이 필요한 부분만 연결하였다.vector>> graph(n+1,vector>());for(int i=0;i>a>>b>>s; graph[b].push_back({a,s});} 답 #include #include #include #include #define ll long longusing namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int t; c.. 2025. 2. 11.
백준 28449 누가 이길까 C++ 간단한 해설  HI팀이 이기는 경우랑 무승부만 세면 자연스럽게 ARC팀이 이기는 경우의 수가 나온다.(전체 경우의 수인 N*M에서 빼면 된다.) 이 때, 전체 경우의 수는 100,000*100,000 이므로 int 자료형의 범위를 넘어가니 long long 형으로 해야한다. HI팀이 이기는 경우의 수는 누적합을 써도 좋지만 나는 간단하게 이분탐색으로 찾았다. upper_bound의 결과값 - lower_bound의 결과값을 하면 간단하게 무승부인 경우의 수를 셀 수 있고,lower_bound의 결과값이 이기는 경우의 수이다. lower_bound는 같거나 큰 값만을 탐색하므로 결과값에서 -1을 해야 하는게 맞지만 Index를 반환하기 때문에(Index가 0부터 시작해서) 따로 처리를 안해주고 결과값 그 .. 2025. 2. 8.

티스토리툴바