백준 1814 : 지붕 색칠하기

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

1814번: 지붕 색칠하기

 

tree dp문제다.

평소에 풀던 tree dp문제는 노드를 칠하거나 칠하지 않거나와 같은 두개의 상태값만 가졌다면, 이 문제는 두 개 이상의 상태값을 가질 수 있는 문제다.

 

이 문제에서 페인트 색깔은 최대 1만개까지 주어지는데 모든 색깔을 다 확인하면 시간초과가 발생하기 때문에 코스트가 낮은 색깔을 적절한 개수만큼 사용하여 문제를 해결해야 한다.

 

색깔은 logN개 만큼 확인해야하는데 그 근거는 아래 링크를 확인 바란다.

https://blog.encrypted.gg/144

[BOJ] 1693번: 트리 색칠하기

 

#include <iostream>
#include <vector>
#include <algorithm>

#define min(a,b) a<b?a:b
using namespace std;

int n;
vector<int> edge[10'001];
vector<int> color;
int dp[10'001][15];
int color_size;

int tree_dp(int cur, int prev, int prev_color) {
	int min_val = 1e9;
	bool flag = 1;
	for (int i = 0; i < color_size; i++) {
		if (i == prev_color) continue;
		if (!dp[cur][i]) flag = 0;
		min_val = min(min_val, dp[cur][i]);
	}
	if (flag) return min_val;


	int next;
	min_val = 1e9;
	for (int cur_color = 0; cur_color < color_size; cur_color++) {
		if (cur_color == prev_color) continue;

		dp[cur][cur_color] = color[cur_color];
		for (int i = 0; i < edge[cur].size(); i++) {
			next = edge[cur][i];
			if (next == prev) continue;

			dp[cur][cur_color] += tree_dp(next, cur, cur_color);
		}
		min_val = min(min_val, dp[cur][cur_color]);
	}

	return min_val;
}

void solution() {
	int n1, n2, m, min_val = 1e9;
	int max_color = 15;

	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> n1 >> n2;
		edge[n1].push_back(n2);
		edge[n2].push_back(n1);
	}

	cin >> m;
	color_size = m < max_color ? m : max_color;
	for (int i = 0; i < m; i++) {
		cin >> n1, color.push_back(n1);
	}
	sort(color.begin(), color.end());

	for (int i = 0; i < color_size; i++) min_val = min(min_val, tree_dp(1, 0, i));

	cout << min_val;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 3412 kb

시간: 12 ms