본문 바로가기
반응형

Problem Solving/BOJ228

백준 10819번 차이를 최대로 - C++(cpp) 풀이 1. N개의 정수의 순서를 정하는 경우의 수는 N! 2. N이 작으므로 모든 경우를 탐색하여 주어진 식이 최대가 되는 경우를 찾는다. 1. N개의 정수의 순서를 정하는 경우의 수는 N! 크기가 N인 배열에 들어있는 수들의 순서를 바꾸는 경우의 수는 N!이다. 2. N이 작으므로 모든 경우를 탐색하여 주어진 식이 최대가 되는 경우를 찾는다. N이 최대 8이므로 8! = 40,320가지밖에 되지 않는다. 따라서 시간 내에 모두 탐색하는 것이 가능하다. 재귀와 비트 마스크를 이용해서 모든 경우를 탐색하고 최대가 되는 경우를 찾으면 된다. #include #include #include using namespace std; int N; int arr[8], pick[8]; int brute_force(int i.. 2022. 5. 3.
백준 2644번 촌수계산 - C++(cpp) 풀이 1. 각 사람을 정점, 부모 자식 관계를 간선으로 연결하면 결과는 트리를 이룬다. 2. 촌수는 트리에서 두 정점 간의 거리와 같다. 3. DFS나 BFS로 두 정점간의 거리를 구한다. 1. 각 사람을 정점, 부모 자식 관계를 간선으로 연결하면 결과는 트리를 이룬다. 부모 자식 관계에서 사이클이 생성되는 것은 불가능하다. 따라서 결과는 항상 트리 구조이다. 2. 촌수는 트리에서 두 정점 간의 거리와 같다. 촌수는 트리에서 두 정점 사이의 간선의 개수, 즉 두 정점간의 거리를 뜻한다. 3. DFS나 BFS로 두 정점간의 거리를 구한다. DFS나 BFS로 두 정점 간의 거리를 구하면 된다. 이때 트리에서 두 정점이 연결되어있지 않으면 촌수를 계산할 수 없는 경우이다. #include #include using.. 2022. 5. 2.
백준 1475번 방 번호 - C++(cpp) 풀이 1. 9는 6이라고 생각하고, 0-8까지 숫자의 등장 횟수를 카운트한다. 2. N개의 숫자 i를 나타내기 위해서는 N개의 세트가 필요하다. 단 6의 경우 한 세트에 6이 두 개씩 들어있으므로(9=6으로 생각하면) ceil(N/2) 개의 세트가 필요하다. 3. 각 숫자를 나타내기 위해 필요한 세트 개수 중 최댓값이 필요한 세트 개수의 최솟값이다. 1. 9는 6이라고 생각하고, 0-8까지 숫자의 등장 횟수를 카운트한다. 6과 9는 뒤집어서 사용할 수 있으므로 같은 숫자로 취급해도 무방하다. 각 숫자의 등장 횟수를 카운트해주는데, 9는 6으로 취급해서 카운트해준다. 2. N개의 숫자 i를 나타내기 위해서는 N개의 세트가 필요하다. 단 6의 경우 한 세트에 6이 두 개씩 들어있으므로(9=6으로 생각하면) cei.. 2022. 4. 19.
백준 14462번 소가 길을 건너간 이유 8 - C++(cpp) 풀이 1. 왼쪽 목초지의 i번째 소를 연결하는 경우, 오른쪽 소 중 가장 앞쪽에 있는 소와 연결하는 것이 최적이다. 2. dp(l, r) = left_cows[l...]과 right_cows[r...] 사이에 놓을 수 있는 횡단보도의 최대 개수 3. dp(l, r) = max(왼쪽의 l번째 소는 연결하지 않는 경우, 왼쪽의 l번째 소와 오른쪽의 i번째 소와 연결하는 경우) 1. 왼쪽 목초지의 i번째 소를 연결하는 경우, 오른쪽 소 중 가장 앞쪽에 있는 소와 연결하는 것이 최적이다. 왼쪽 목초지의 소를 기준으로 차례로 연결한다고 하면, 횡단보도가 겹치지 않기 위해서는 연결시키는 오른쪽 목초지의 소도 오름차순이어야 한다. 즉, 더 나중에 매칭하는 오른쪽 소의 번호가 작아지면 안 된다. 이전 매칭에서 최대한 앞쪽의.. 2022. 4. 17.
백준 13418번 학교 탐방하기 - C++(cpp) 풀이 1. 최소한의 길을 선택해서 모든 건물을 탐방해야 하므로, 스패닝 트리를 구하면 된다. 2. 오르막길에는 가중치 1, 내리막길에는 가중치 0을 준다. 3. 최악의 경로는 최대 스패닝 트리, 최적의 경로는 최소 스패닝 트리이다. 1. 최소한의 길을 선택해서 모든 건물을 탐방해야 하므로, 스패닝 트리를 구하면 된다. 모든 건물을 방문하는 데 필요한 최소한의 길을 선택해야 한다. 즉, 최소 연결 부분 그래프 = 스패닝 트리를 구하면 된다. 모든 건물을 방문하려면 왔던 길을 되돌아가야 하기 때문에 문제가 생기지는 않을까 싶지만, 오르막길은 되돌아갈 때는 내리막길이 되고, 또 내리막길이 되돌아올 때 오르막길이 되는 것은 무효 처리하기 때문에 단순히 스패닝 트리를 구해도 문제가 되지 않는다. 2. 오르막길에는 가중.. 2022. 4. 15.
반응형

티스토리툴바