BOJ)2337 트리 자르기

문제: icpc.me/2337

트리에서 임의의 몇개의 간선을 잘라서 크기가 m인 트리를 얻고 싶을 때 잘라야하는 간선의 최소 개수를 구하는 문제이다.

트리디피로 풀 수 있는 문제이다. 기존에는 트리 디피를 n^3의 방법으로 풀어왔지만 이번에 smu형님의 도움으로 n^2 log n으로 푸는 방법을 알게 되었다.

우선 dp테이블을 dp[here][k]를 here번 정점이 루트인 크기가 k인 트리를 만드는데 필요한 간선컷의 최솟값으로 정의하면

dp[here][k]를 어떤식으로 빌드할거냐면 here가 가지는 자식들은 여러개의 서브트리를 이룰것이다.

이 서브트리를 하나씩 병합하면서 dp[here][k]를 채울 것이다.

당연히 처음에는 dp[here][1]밖에 없을 것이다 .여기서 1은 곧 자기 자신이다 이는 0으로 초기화해주고

모든 자식에 대해서 빌드를 할건데 자식에 대한 dp값을 먼저 채워져있다고 가정한 뒤

나의 size에 대한 이터레이터를 i  나의 자식의 size 에대한 이터레이터를 j라고 한다면

dp[here][i+j]=min(dp[here][i]+dp[next][j], dp[here][i+j]) 가 될것이다. 

이 때 예외로 j가 0인 경우는 dp[here][i+j]=min(dp[here][i]+1,dp[here][i+j])이다. 왜냐하면 j가 0인 경우는 현재 병합하려는 서브트리를 아예 선택하지 않는 경우니까 서브트리의 루트와 연결 된 간선을 자르는 의미가 된다 그래서 +1이 붙게 된다.

이러한 점화식으로 채워주면 이중 포문이 sz[here] ,sz[next]만큼 돌게 된다. 이는 n^2이 아니고 잘은 모르겠지만 부분 문제를 해결하는 시간복잡도 계산? 에 의하여 nlogn에 수렴한다고 한다.

그래서 n^2 log n 에 점화식을 채워줄 수 있다. 하지만 이대로 구현하면 틀리게된다.

주의할 점이 있는데 dp테이블을 저렇게 빌드하면서 병합하면 하나의 서브트리와 병합할 때 dp[here][i+j]값이 중복되어 계산될 수 있다.  그렇기 때문에 그런 경우를 방지하기 위하여

dp[here][i+j]들을 tmp[i+j]라는 배열에 따로 저장을 해주어 하나의 서브트리에 대한 병합이 다 끝나고 난 이후에 tmp[i+j]를 dp[here][i+j]로 옮겨주는 작업을 수행해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int dp[155][155], n, m, x, y, sz[155], tmp[155], res;
vector<vector<int>> vt;
void dfs(int here, int par) {
    sz[here] = 1;
    dp[here][1] = 0;
    for (int next : vt[here]) {
        if (next == par)continue;
        dfs(next, here);
        memset(tmp, 0x3f, sizeof(tmp));                    
        for (int i = 1; i <= sz[here]; i++) {
            for (int j = 0; j <= sz[next]; j++) {
                if (!j)tmp[i + j] = min(tmp[i + j], dp[here][i] + 1);    //j가 0이라는건 자식을 잘라내겠다는 걸 의미
                else
                    tmp[i + j] = min(tmp[i + j], dp[here][i] + dp[next][j]);
            }
        }
        sz[here] += sz[next];
        for (int i = 1; i <= sz[here]; i++)
            dp[here][i] = tmp[i];
    }
}
int main() {
    scanf("%d%d", &n, &m);
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d", &x, &y);
        vt[x].push_back(y);
        vt[y].push_back(x);
    }
    memset(dp, 0x3f, sizeof(0x3f));
    dfs(1, 0);
    res = 1e9;
    for (int i = 1; i <= n; i++)
        if(sz[i]>=m)
        res = min(res, dp[i][m] + (i == 1 ? 0 : 1));//i가 1이 아니라면 i번 정점이 루트가 되려면 컷이 한번 필요함 
    printf("%d\n", res == 1e9 ? -1 : res);
    return 0;
}