트리에서의 다이나믹 프로그래밍 (3) 썸네일형 리스트형 백준 8872번 빌라봉 https://www.acmicpc.net/problem/8872 8872번: 빌라봉첫째 줄에는 N, M, L이 주어진다. 둘째 줄부터 M개 줄에는 A[i] B[i] T[i]가 주어진다. 1 ≤ N ≤ 100,000 0 ≤ M ≤ N-1 0 ≤ A[i], B[i] ≤ N-1 1 ≤ T[i] ≤ 10,000 1 ≤ L ≤ 10,000www.acmicpc.net 일단 각각의 연결된 빌라봉들이 트리형태이니 연결된 빌라봉들마다 한번씩 dfs를 돌려야 할 것 같다.그리고 그 트리가 다른 트리들과 연결될때는 하나의 노드에서만 연결되고 트리에서 그 노드로부터 가장 먼 정점의 거리가 가장 짧게되는 정점을 잡으면 된다.이때 트리마다 나오는 이 거리들을 그 트리의 가중치로 두면 각 트리를 정점으로 하는 큰 트리가 만들어 .. 백준 1967번 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연www.acmicpc.net트리디피와 그리디로 각각 문제를 풀었다. 트리DP 풀이트리의 지름은 지름이 지나는 가장 깊이가 낮은 노드를 루트로 하는 서브트리에 포함된다.이때 해당 노드를 한 끝점으로 하는 경우와 노드를 지나면서 자식 노드들 중 둘을 지나는 경우로 나눌 수 있다. dp[a]를 a번 노드를 루트로 하면서 자식 노드들 중 하나만을 지나는 경로의 길이로 하였고 모든 노드에 대해 최대 두개의 자식 노드.. 백준 2197번 분해 반응 https://www.acmicpc.net/problem/2197 2197번: 분해 반응첫째 줄에 두 정수 N, M(1≤M≤N)이 주어진다. 다음 N-1개의 줄에는 원자들의 연결 상태를 나타내는 서로 다른 두 정수 A, B(1≤A, B≤N)가 주어진다. 이는 A번 원자와 B번 원자가 결합을 이루고 있다는www.acmicpc.netN이 작아서 dp를 좀 복잡하게 짜도 된다.나는 N*(N + 1)로 벡터를 만들어서 dp[i][j] = i번 노드를 루트로 하는 j개의 노드를 가진 서브트리의 최소 분해 반응 회수로 두었고 부모노드와 자식노드의 서브트리를 합칠때 노드 수는 더해지고 문해 반응 횟수는 서로를 연결하는 간선을 제외해서 둘의 값을 더하고 2를 빼면 되니 점화식은 dp[i][j + n] = min(dp[.. 이전 1 다음
