백준1693 트리 색칠하기

작성일 | In

문제 링크

  • http://icpc.me/1693

사용 알고리즘

  • Tree DP

시간복잡도

  • O(n log n)

풀이

문제를 보자마자 Tree DP인 것 같았습니다.
dp[i][j] = i번 정점을 j로 색칠했을 때, i를 루트로 하는 서브트리의 최소 비용 으로 dp배열을 정의하고 코딩을 하려고 했지만, n이 최대 100,000이기 때문에 O(n2)은 불가능합니다.
탐색 범위를 줄여봅시다.

(이 글) 에서 koosaga님의 답변 내용을 통해 최대 log2n개의 색만 이용해 답을 구할 수 있습니다. 그러므로 시간복잡도는 O(n log n)이 됩니다.

다른 tree dp 문제와 비슷하게 dfs tree를 생성해 트리의 탐색 순서를 정하고, 메모이제이션을 이용해 답을 구해주면 됩니다.

전체 코드

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
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[101010][20]; //n번째 정점을 n으로 색칠할 때의 최소 비용
vector<int> input_g[101010];
vector<int> g[101010];
int n;

void makeDfsTree(int now, int prv){
	for(auto nxt : input_g[now]){
		if(nxt != prv){
			g[now].push_back(nxt);
			makeDfsTree(nxt, now);
		}
	}
}

ll solve(int now, int color){
	ll &res = dp[now][color];
	if(res != -1) return res;

	ll prv = 0;

	for(auto nxt : g[now]){
		ll tmp = 1e16;
		for(int i=1; i<20; i++){
			if(color==i) continue;
			tmp = min(tmp, solve(nxt, i));
		}
		prv += tmp;
	}
	return res = prv + color;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<n; i++){
		int a, b; cin >> a >> b;
		input_g[a].push_back(b);
		input_g[b].push_back(a);
	}
	makeDfsTree(1, 1);
	memset(dp, -1, sizeof(dp));

	ll ans = 1e16;
	for(int i=1; i<20; i++){
		ans = min(ans, solve(1, i));
	}

	cout << ans;
}