[백준/BOJ] 백준 1814번 : 지붕 색칠하기

www.acmicpc.net/problem/1814

1814번: 지붕 색칠하기

트리DP(트리에서 다이나믹 프로그래밍)을 이용해 문제를 해결했다. 주의해야 될 점은 2의 n-1승개의 노드를 칠한다면 n개의 색깔만 고려하면 충분하다는 것(이 부분 맞는지 다시 확인)을 배웠다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> adj[10001];
int m;
vector<int> paint;
long long cache[10001][15]; //2의 13승 < 10000 < 2의 14승 , 10000은 2의 13.xx 승이라고 하면, 10000개의 노드를 칠하는데 15개의 색깔이면 된다
vector<int> maked(10001, 0);

void Pre()
{
	for (int i = 1; i <= 10000; i++)
		for (int j = 0; j < 15; j++)
			cache[i][j] = -1;
}

struct node
{
	int number;
	vector<node*> children;
};

node* makeTree(int root)
{
	node* ret = new node();
	ret->number = root;

	//root번 노드를 만들었다고 체크
	maked[root] = 1;

	for (int i = 0; i < adj[root].size(); i++)
	{
		//길로 연결된 집 중에서 노드로 만들어 지지 않은 집들만 트리로 만들어서 children으로 저장한다
		if (maked[adj[root][i]] == 0)
			ret->children.push_back(makeTree(adj[root][i]));
	}

	return ret;
}

//root노드를 color색으로 칠할때 root노드가 루트인 서브트리의 최소비용
long long solve(node* root, int color)
{
	long long& ret = cache[root->number][color];

	//ret가 -1이 아니면 계산한적 있는 값이다
	if (ret != -1)
		return ret;

	//잎노드일때
	if (root->children.size() == 0)
		return (long long)paint[color];

	//root노드의 집에 color색을 칠하는 비용
	ret = (long long)paint[color];

	//자식 노드들을 돌면서 자식노드에 어떠한 색을 칠했을때 자식노드가 루트인 서브트리가 최소비용인 경우를 찾는다
	for (int i = 0; i < root->children.size(); i++)
	{
		long long min_value = numeric_limits<long long>::max(); //초기에는 굉장히 큰 값을 넣어둔다

		if (m < 15)
		{
			for (int j = 0; j < m; j++)
			{
				if (color != j)
					min_value = min(min_value, solve(root->children[i], j));
			}
		}

		else
		{
			for (int j = 0; j < 15; j++)
			{
				if (color != j)
					min_value = min(min_value, solve(root->children[i], j));
			}
		}

		ret += min_value;
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;

		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int input;
		cin >> input;

		paint.push_back(input);
	}

	sort(paint.begin(), paint.end()); //페인트의 가격이 낮은 15개 페인트 이하의 것만 사용할것이다

	//1번 노드를 루트로 하는 트리로 만든다
	node* root = makeTree(1);

	long long result = numeric_limits<long long>::max();

	if (m < 15)
	{
		for (int i = 0; i < m; i++)
		{
			//루트에 색을 칠해보며 그 중 전체 비용의 최솟값을 찾는다
			result = min(result, solve(root, i));
		}
	}

	else
	{
		for (int i = 0; i < 15; i++) //2의 13승 < 10000 < 2의 14승 , 10000은 2의 13.xx 승이라고 하면, 10000개의 노드를 칠하는데 15개의 색깔이면 된다
		{
			//루트에 색을 칠해보며 그 중 전체 비용의 최솟값을 찾는다
			result = min(result, solve(root, i));
		}
	}

	cout << result;

	return 0;
}