본문 바로가기
반응형

Problem Solving242

백준 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.
백준 10986번 나머지 합 - C++(cpp) 풀이 1. s부터 e까지의 구간합이 M으로 나누어 떨어지려면, psum[e] % M = psum[s-1] % M이어야 한다. 2. psum[i] % M = psum[j] % M 인 (i, j) 쌍의 개수를 구한다. 3. psum[i] % M 자체가 0인 경우도 추가로 카운트한다. 1. s부터 e까지의 구간합이 M으로 나누어 떨어지려면,psum[e] % M = psum[s-1] % M이어야 한다. i까지의 누적합을 psum[i]라고 하자. s부터 e까지의 구간합은 psum[e] - psum[s-1]이 된다. 이 구간합이 M으로 나누어 떨어지려면, (psum[e] - psum[s-1]) % M = 0이어야하므로, psum[e] % M = psum[s-1] % M이 성립해야 한다. 2. psum[i] % M = p.. 2022. 4. 14.
반응형

티스토리툴바