BOJ 11808 - 마리오와 사악한 키노피오

문제 요약

 

정점 \(N \leq 1000\) 개로 이루어진 트리가 있을 때, 루트를 제외한 정점 \(K \leq 100\)개를 선택해 순서대로 방문할 것이다. 이 때, 정점 간 이동은 항상 최단거리로 진행한다. 정점 \(K\)개와 순서를 잘 정해 이동거리의 합이 최대가 되게 하여라.

 

풀이

문제 조건이 독특해 약간 헤멨다. 우선, 제한이 적으므로 \(dp[v][i]\)를 \(v\)번 정점을 루트로 하는 서브트리에서 \(i\)개를 선택해 나올 수 있는 최적해로 정의하자. 이제 각 정점에서 해야 할 일은 자식 노드들의 DP값을 잘 합쳐주는 것이다. 이는 \(dp[v][i]\)를  \(dp[v][j]\)와 \(dp[c][i-j]\)로 분해해서 생각해주면 된다. 두 값은 이미 정해져 있으니 더해주어야 할 값은 두 노드 사이의 간선을 몇 번 지나는지인데, 이 부분이 제일 어려운 부분이다.

 

단순히 생각해보면, 당장 서브트리 밑쪽으로는 정점이 \(i-j\)개, 서브트리 위쪽으로는 정점이 \(j\)개 있으므로 \(2 min(i-j,j)\)번 지날 것 같다. 하지만, 그렇지 않다. 이 경우 \(i=3, j=1\)과 같은 경우일 때 이미 전에 처리한 간선의 값을 다시 더해주어야 하는데, 이러면 시간 내에 해결하기가 어렵다.

 

위에서 생각했던 방법을 다시 생각해보면, 어차피 결국 선택되는 정점은 \(K\)개이므로 서브트리 위쪽 정점은 무조건 \(K-j\)개이다. 이 때, 1번 정점은 어차피 시작 정점이라 방문하게 되므로 \(K-j+1\)개라고 생각하면, 해당 간선을 지나는 횟수는 \(2 min(j, K-j+1)\)번이다. 이를 잘 처리해주면 된다.

 

각 정점은 딱 한 번만 다른 정점과 합쳐지고, 한 번 합치는 데에 \(O(K^2)\)이므로 전체 시간복잡도는 \(O(N K^2)\)이다. 구현상 주의할 점이 있다면, 서브트리를 모두 합치고 루트 노드를 선택해줄 경우를 고려할 때 1번 노드를 제외해야 한다는 점과 DP값을 갱신해줄 때 현재 갱신된 값이 다시 갱신에 고려되지 않게 처리해주어야 한다는 점이다.

 

+KOI 검은 돌과 같은 원리로 시간복잡도 \(O(N^2)\)에도 해결할 수 있다고 한다. (by slah007) 그런데 실행시간이 \(O(NK^2)\)가 훨씬 적다.. 뭐지?

 

여담으로, Class 9 문제들을 풀다 느끼는 점은 기여하기가 상당히 힘들다는 것이다. 내가 다이아 문제들을 많이 풀어보지 않은 점도 있고, 기여 수가 많지 않아 어제 오늘 연속으로 내 기여로 티어가 바뀌어버렸다. 기여 신중히 해야지..