트리에서의 다이나믹 프로그래밍 2편 [끝]
안녕하세요, 이번 게시물에서는 트리에서의 다이나믹 프로그래밍 특정 유형을 풀이하는 방법을 다뤄보려고 해요. 이 게시물에서 다루는 풀이를 적용하기 위해서는 문제 상황이 아래와 같아야 해요. 1. n개의 정점과 n - 1개의 간선으로 이루어진 트리이어야 한다. 2. n2개의 모든 정점의 쌍인 (i, j)에 대하여 두 개의 정점 (i, j) 최단 거리의 총합을 O(n)에 구해야 한다. (최단 거리는 꼭 가중치의 합이 아니어도 된다. 가중치의 곱이 될 수도 있다.) 위 조건을 만족시키는 문제 네 개 정도에 적용해보았는데, 모두 적용할 수 있었어요. BOJ 1289 - 트리의 가중치 Platinum 3 BOJ 20188 - 등산 마니아 Platinum 5 BOJ 7812 - 중앙 트리 Platinum 5 BOJ ..
2024.03.10
