αλγριθμο

문제 https://www.acmicpc.net/problem/2315 2315번: 가로등 끄기 첫째 줄에는 2개의 정수 N(1 ≤ N ≤ 1,000), M 이 있다. 첫 번째 정수 N은 가로등의 개수를 나타내는 정수이고, 두 번째 정수 M은 마징가 처음에 위치하는 가로등 번호이다. 다음 N 개의 줄에는 각 가 www.acmicpc.net 알고리즘 DP 누적 합 풀이 만약, \(i\)번째 가로등에서 \(j\)번째 가로등을 끄기 위해 이동한다면, 두 가로등 사이에 있는 가로등은 지나가면서 끄는게 가장 효율적입니다. 그러므로, \(i\)번째와 \(j\)번째 가로등이 꺼져 있다는 것은, 두 가로등 사이의 가로등도 꺼져 있다는 뜻입니다. 따라서, 가로등에 대한 정보가 주어졌을 때, 다음 \(3\)개의 배열을 만..

문제 https://www.acmicpc.net/problem/2647 2647번: 검은점과 하얀점 연결 2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점이다. 하나의 검은 점과 하나의 하얀 점을 연결하여 한 쌍을 만들면, 모두 n개의 쌍이 만들어진다. 한 쌍의 점 www.acmicpc.net 알고리즘 DP 풀이 DP 역추적 문제입니다. 점들에 대한 정보가 주어졌을 때, 다음 \(3\)개의 배열을 만들어 정의할 수 있습니다: \(dp[i][j]:\) \(i\)번째부터 \(j\)번째까지의 점으로 길을 만들 때, 길의 거리의 합의 최솟값. \(hgt[i][j]:\) \(i\)번째부터 \(j\)번째까지의 점으로 길을 만들 때, 높이가 가장 높은 길의 높이(..

문제 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 알고리즘 DP 풀이 점화식을 세우는 것이 조금 어려웠습니다. 하지만 점화식만 잘 세우면 구현과 역추적은 쉽습니다. 배열 \(2\)개를 만들어 다음과 같이 정의합니다; \(dp[i][j]:\) 두 경찰차가 마지막으로 처리한 사건이 각각 \(i, j\)일 때(두 경찰차의 위치가 각각 사건 \(i\), 사건 \(j\)의 위치일 때), 마지막으로 처리된 사건의 다음 사건부터 마지막 사..

문제 https://www.acmicpc.net/problem/17422 17422번: 지폐가 넘쳐흘러 첫째 줄에 금고의 개수 N이 주어진다. 양의 정수 k에 대해, N = 2k-1이 항상 성립한다. 둘째 줄에 금고에 들어 있는 지폐의 개수 Wi가 1번 금고부터 순서대로 주어진다. 셋째 줄에 놀이의 횟수 Q가 www.acmicpc.net 알고리즘 트리DP 우선순위 큐 풀이 트리와 각 금고의 지폐의 개수 \(W_{i}\)가 주어졌을 때, 두 배열 \(A, B\)를 만들어 다음과 같이 정의합니다: \(A_{i}:\) \(i\)을 루트로 하는 서브트리 안에 있는 한 리프 노드로부터 \(n\)까지의 경로에 있는 지폐 개수의 최대값. \(B_{i}:\) \(i\)을 루트로 하는 서브트리 안에 있는 지폐 개수의 합..

문제 https://www.acmicpc.net/problem/20506 20506번: Kaisar - 생존 준원이(0/5/3)는 생존해있는 카이사(2/7/0)를 찾으러 소환사의 협곡을 수색하고 있다. 협곡은 정점이 N개 있는 트리 모양이고, 정점은 1번 정점에서 N번 정점까지 번호 붙여져 있다. 준원이는 모든 www.acmicpc.net 풀이 트리DP를 사용합니다. 트리가 주어졌을 때 다음 \(2\)개의 배열을 정의합니다: \(cnt[i]:\) \(i\)를 루트로 하는 서브트리의 크기. (노드의 개수) \(dp[i]:\) \(i\)를 \(lca\)로 가지는 두 노드의 쌍의 개수. \(dp[i]\), 즉, \(i\)를 \(lca\)로 가지는 두 노드의 쌍의 개수를 구하는 방법은 다음과 같습니다: \(i\..

문제 https://www.acmicpc.net/problem/15669 15669번: 나무 위의 입자 트리란, 사이클이 없는 연결 그래프를 의미한다. 위 그림은 트리 모양의 입자가속기와 그 위의 어떤 정점에 놓인 특별한 입자 하나를 표시하고 있다. RB 입자라고 불리는 이 특이한 입자는 안정 www.acmicpc.net 풀이 트리DP를 사용합니다. 트리가 주어졌을 때, 두 배열을 만들어 다음과 같이 정의합니다: \(depth[i]:\) 노드 \(i\)의 깊이. \(dp[i][0], dp[i][1]:\) \(i\)를 루트로 하는 서브트리의 노드 중 깊이가 짝수인 노드의 개수, 홀수인 노드의 개수. 트리를 순회하면서 위 두 배열에 값을 저장한 다음 각 \(M\)개의 쿼리에 대하여 다음 작업을 수행합니다. ..

문제 www.acmicpc.net/problem/1693 1693번: 트리 색칠하기 n개의 정점으로 이루어진 트리가 있다. 이 트리의 각 정점을 색칠하려고 한다. 색칠을 할 때에는 1, 2, 3, …, n번 색깔 중에 하나로 색칠하여야 한다. 각 색깔을 사용하여 한 개의 정점을 색칠할 때 www.acmicpc.net 풀이 트리DP를 사용합니다. 트리가 주어졌을 때 배열 \(dp\)를 다음과 같이 정의할 수 있습니다: \(dp[i][j]:\) \(i\)의 색이 \(j\)일 때 \(i\)를 루트로 하는 서브트리의 총 비용의 최솟값. 여기서 \(j\)를 \(1\)부터 \(N\)까지 전부 다 구하면 \(N\)의 범위가 \(1\)이상 \(100000\)이하이기 때문에 시간초과가 날 수 있습니다. www.acmic..

문제 www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 풀이 트리DP를 사용합니다. 먼저, 예제에서 나온 트리를 보겠습니다. 위 트리의 \(A\)노드에서 다른 모든 노드들로 이동할 때, 각 간선이 이용되는 횟수는 다음과 같습니다. \(A\)를 루트로 하여 트리를 순회하면서 각 \((B, C, D, E)\)를 루트로 하는 서브 트리의 크기(노드의 개수, 즉, 루트라고 하는 노드와 그 노드의 부모와 이어지는 간선이 이용되는 횟수)에 그 간선의..