본문 바로가기

알고리즘 관련/BOJ

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]로 옮겨주는 작업을 수행해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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, 0x3fsizeof(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, 0x3fsizeof(0x3f));
    dfs(10);
    res = 1e9;
    for (int i = 1; i <= n; i++)
        if(sz[i]>=m)
        res = min(res, dp[i][m] + (i == 1));//i가 1이 아니라면 i번 정점이 루트가 되려면 컷이 한번 필요함 
    printf("%d\n", res == 1e9 -: res);
    return 0;
}
cs



'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13352 석양이 진다...  (1) 2017.09.07
BOJ)5842 Partitioning the Farm  (0) 2017.09.07
BOJ)11003 최소값 찾기  (1) 2017.09.05
BOJ)1460 진욱이의 농장  (0) 2017.09.05
BOJ)13548 수열과 쿼리 6  (0) 2017.09.03