본문 바로가기
반응형

Problem Solving242

백준 2210번 숫자판 점프 - C++ 풀이 1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다. 1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다. 5번 이동하므로 총 탐색해야 하는 상태 수는 25 * (4^5)로 매우 적기 때문에 브루트 포스로 해결할 수 있다. DFS를 통해 모든 경우를 구해서, 만들 수 있는 모든 수를 구해준다. #include #include using namespace std; int board[5][5]; unordered_set st; int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; void DFS(int n, int r, int c, int curr) { if (n == 6) { st.insert(curr); return; } fo.. 2022. 9. 6.
백준 2607번 비슷한 단어 - C++ 풀이 1. 같은 구성을 갖는 경우, 모든 알파벳의 등장 횟수가 같다. 2. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, 한 알파벳만 등장 횟수가 1 차이 난다. 3. 한 문자를 다른 문자로 바꾸면 같은 구성을 갖는 경우, 두 알파벳의 등장 횟수가 각각 -1, 1 씩 차이 난다. 1. 같은 구성을 갖는 경우, 모든 알파벳의 등장 횟수가 같다. 알파벳의 위치(순서)는 중요하지 않다. 각 알파벳의 등장 횟수만 같다면 같은 구성을 갖는다. 따라서 단어마다 각 알파벳의 등장 횟수를 세준다. A-Z까지 등장 횟수가 모두 일치한다면, 처음부터 같은 구성을 갖는 경우이다. 2. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, 한 알파벳만 등장 횟수가 1 차이 난다. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, .. 2022. 9. 5.
백준 4716번 풍선 - C++ 풀이 1. DA와 DB의 차가 큰 순으로 풍선을 배부한다. 1. DA와 DB의 차가 큰 순으로 풍선을 배부한다. A 풍선과 B 풍선의 합은 항상 K로 유지되어야 한다. 따라서 풍선이 모자라서 더 먼 곳을 택해야할 때 생기는 손해가 가장 큰 팀에게 먼저 풍선을 배부해서 손해를 줄여야 한다. 즉, | DA-DB | 값 내림차순으로 정렬한 뒤, 각 팀의 이동 거리가 최소가 되도록 배부해준다. #include #include #include using namespace std; typedef long long ll; struct Team { int k, da, db; }; int N, A, B; vector teams; bool cmp(const Team& lhs, const Team& rhs) { return ab.. 2022. 9. 3.
백준 2632번 피자판매 - C++ 풀이 1. B피자에서 연속된 조각을 선택하는 모든 경우를 구해 각 연속합을 만들 수 있는 경우의 수를 구해둔다. 2. A피자에서 연속된 조각을 선택하는 모든 경우에 대해 목표합을 만들기 위한 경우의 수를 더한다. 1. B피자에서 연속된 조각을 선택하는 모든 경우를 구해 각 연속합을 만들 수 있는 경우의 수를 구해둔다. 두 피자에서 연속된 조각을 선택하는 모든 경우를 고려하면 O(N^4)의 시간 복잡도가 소요된다. 따라서 두 피자를 각각 탐색한 뒤, A피자를 기준으로 대응하는 B 피자의 경우의 수를 구하는 방법을 사용하여 O(N^2)에 해결할 것이다. mp[i] = (B 피자에서 연속합이 i가 되도록 조각을 고르는 경우의 수)라고 하자. B 피자에서 연속된 조각을 선택하는 모든 경우에 대해 그 합을 구해 mp .. 2022. 9. 2.
백준 14867번 물통 - C++ 풀이 1. 항상 두 물통 중 한 물통은 꽉 차있거나 비어있다. 2. BFS를 사용해서 {0, 0}에서 {C, D}로 가는 최단 거리를 구한다. 1. 항상 두 물통 중 한 물통은 꽉 차있거나 비어있다. 주어진 연산을 사용하면 항상 두 물통 중 한 물통은 꽉 차있거나 비어있어야 한다. 따라서 상태를 나타낼 때, 아래와 같은 3가지 정보만 있으면 된다. 한 물통에 들어있는 양 x 그 물통이 A물통인지 B물통인지 여부 반대 물통이 비어있는지 꽉 차있는지 여부 두 물병에 들어있는 물의 양 정보 대신 위의 정보를 사용하여 상태를 나타내면 상태 개수를 N^2개에서 4N개로 줄일 수 있다. 2. BFS를 사용해서 {0, 0}에서 {C, D}로 가는 최단 거리를 구한다. 위의 사실을 이용해서 상태 노드를 나타내고 BFS를 사.. 2022. 9. 1.
반응형

티스토리툴바