[백준/BOJ] 백준 16468번 : 크리스마스 트리 꾸미기

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

16468번: 크리스마스 트리 꾸미기

cache[트리높이][볼 개수]에 해당 트리높이에서 해당 볼 개수를 가지고 있을 때 만들어질 수 있는 트리의 경우의 수를 저장하는 방법으로, 트리에서 다이나믹 프로그래밍(트리 DP)을 이용해 문제를 해결했다.

 

height높이의 트리를 ball_cnt개의 공으로 만드는 경우의 수를 구할때, 왼쪽 자식의 트리 또는 오른쪽 자식의 트리 중 최소 하나는 height - 1 높이의 트리를 가져야 하므로, 왼쪽 자식의 트리와 오른쪽 자식의 트리 둘다 height-1 높이의 트리가 만들어지는 경우, 왼쪽 자식의 트리만 height-1 높이의 트리가 만들어지는 경우, 오른쪽 자식의 트리만 height-1 높이의 트리가 만들어지는 경우로 나누어서 경우의 수를 구했다.

 

코드

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

int n, l;
long long cache[305][305]; //[트리높이][볼 개수] = 해당 트리높이에서 해당 볼 개수를 가지고 있을때 만들어질 수 있는 트리의 경우의 수

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

long long Solve(int height, int ball_cnt) {

	long long& ret = cache[height][ball_cnt];

	if (ret != -1) {
		return ret;
	}

	//한줄로된 트리로 만들어도 트리를 만들 수 없을때
	if (ball_cnt < height) {
		return 0;
	}

	//리프노드일때
	if (height == 1) {
		if (ball_cnt == 1) {
			return 1;
		}
		else {
			return 0;
		}
	}

	//만들 트리의 높이가 0일때
	if (height == 0) {
		if (ball_cnt == 0) {
			return 1;
		}
		else {
			return 0;
		}
	}

	ball_cnt--;//현재위치에서 ball을 하나 씀

	ret = 0;
	for (int i = 0; i <= ball_cnt; i++) {

		int left_ball_cnt = i; //왼쪽 자식노드에 배분할 공 개수
		int right_ball_cnt = ball_cnt - i; //오른쪽 자식노드에 배분할 공 개수

		//왼쪽 자식의 트리나 오를쪽 자식의 트리중 최소 하나는 height-1 높이의 트리를 만들어야 된다
		//두개 중 하나가 height-1 높이의 트리가 만들어지면 나머지 하나는 어떤 높이의 트리가 만들어져도 상관이 없다  

		long long left_result = (Solve(height - 1, left_ball_cnt) + 100030001) % 100030001;
		long long right_result = (Solve(height - 1, right_ball_cnt) + 100030001) % 100030001;

		//왼쪽 자식의 트리와 오른쪽 자식의 트리 둘다 height-1 높이의 트리가 만들어지는 경우에 ret에 값이 추가 된다
		ret += (((left_result * right_result) + 100030001) % 100030001);

		if (left_result != 0) { //왼쪽 자식의 트리가 높이 height-1의 트리가 만들어졌을때

			//오른쪽 자식의 트리는 right_ball_cnt개의 공으로 0에서 height-2사이의 높이 트리중 아무거나 만들어지면 된다
			//즉, 왼쪽 자식의 트리는 height-1높이의 트리가 만들어 지고, 오른쪽 자식의 트리는 height-1미만 높이의 트리가 만들어질때
			long long right_add = 0;
			for (int j = 0; j <= height - 2; j++) {
				right_add += ((Solve(j, right_ball_cnt) + 100030001) % 100030001);
			}

			ret += (((left_result * right_add) + 100030001) % 100030001);
		}

		if (right_result != 0) { //오른쪽 자식의 트리가 높이 height-1의 트리가 만들어졌을때

			//왼쪽 자식의 트리는 left_ball_cnt개의 공으로 0에서 height-2사이의 높이 트리중 아무거나 만들어지면 된다
			//즉, 오른쪽 자식의 트리는 height-1높이의 트리가 만들어 지고, 왼쪽 자식의 트리는 height-1미만 높이의 트리가 만들어질때
			long long left_add = 0;
			for (int j = 0; j <= height - 2; j++) {
				left_add += ((Solve(j, left_ball_cnt) + 100030001) % 100030001);
			}

			ret += (((right_result * left_add) + 100030001) % 100030001);
		}

	}

	return ret % 100030001;
}

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

	Pre();

	cin >> n >> l;

	cout << Solve(l, n);

	return 0;
}