백준 1772 정원 정리

https://www.acmicpc.net/problem/1772

1772번: 정원 정리

2197, 2337과 같은 문제. O(n^3)에 푼 것 같다. 

 

루트를 하나 잡고, 그 지점을 포함하는 트리만을 생각했다. 이게 n^2에 되서, 모든 지점에 대해 반복할 수 있다. 

 

DP를 하는데, 각 지점에 대해 dp[i][j]를 i번 정점을 루트로 하는 서브트리에서 j개를 잘라내기 위해 필요한 최소 커팅 수로 잡자. 그러면, DFS를 돌면서 dp를 업데이트할 것인데, s라는 정점을 볼 때 그 정점의 서브트리들의 DP값을 알고 있을 것이다. 한번에 합치는 건 힘들고, 각 서브트리의 dp값을 하나하나 보면서 지금까지 본 서브트리로 저장한 dp[s]에서의 dp값과 보고 있는 서브트리 dp[child]에서의 dp값을 잘 조합해서 dp[s]를 업데이트하면 된다.

업데이트 방식

for(int i=sz[s];i>=0;i--)
    for(int j=0;j<=sz[child];j++)
        dp[s][i+j]=min(dp[s][i+j], dp[s][i]+dp[child][j]);
sz[s]+=sz[next];

이렇게 업데이트하면 모순되는 부분 없이 자르는게 가능하다는 걸 생각해 볼 수 있다. 그리고 그 서브트리 전체를 잘라내는 것을 생각해서 dp[i][sz[i]]=1로 두면 된다. 결국 답은 dp[root][n-m]이 된다. 

 

그리고, 서브트리끼리 DP값을 합쳐나가는 과정의 시간복잡도가 두 서브트리의 크기의 곱으로 나타나기에, O(n^2)이라고 두면 k^2/2 + kl + l^2 이 (k+l)^2이 되어서 귀납적으로 O(n^2) 이라고 생각해 볼 수 있다.