백준 1234 / C++

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

1234번: 크리스마스 트리

 

[ 풀이 ] 

dp[h][r][g][b]를 h높이를 채울 것이고 지금까지 r, g,b만큼 색상을 쓴 경우의 수라고 하자. 

상태전이는 다음과 같다.

1. 한 색으로 h칸을 모두 칠한다. : dp[h+1][r+h][g][b] 로 전이 (g, b도 마찬가지)

2. h가 짝수면 두개를 골라 절반씩 칠한다.

: dp[h+1][r+h/2][g+h/2][b] * h!/(h/2)!(h/2)! 로 전이 (g, b도 마찬가지)

3. h가 3의 배수면 dp[h+1][r+h/3][g+h/3][b+h/3]*h!/(h/3)!^3 으로 전이 

기저조건은 h=n+1일때 (다 채움) r<=R , g<=G, b<=B면 색을 R,G,B양으로 잘 칠한것이므로 1을 리턴해주면 된다.

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, R, G, B, fac[12], dp[12][111][111][111];

void make_table() {
	fac[0] = 1;
	for (ll i = 1; i <= 11; i++) {
		fac[i] = i * fac[i - 1];
	}
}

ll mul(ll n, ll r) {
	if (r == 2) return fac[n] / fac[n / 2] / fac[n / 2];
	if (r == 3) return fac[n] / fac[n / 3] / fac[n / 3] / fac[n / 3];
}

ll go(int h, int r, int g, int b) {
	if (h == n + 1) return (r <= R && g <= G && b <= B); // base case
	ll& ret = dp[h][r][g][b];
	if (~ret)return ret;
	ret = 0;
	// 1 color
	ret += go(h + 1, r + h, g, b);
	ret += go(h + 1, r, g + h, b);
	ret += go(h + 1, r, g, b + h);
	// 2 color
	if (h % 2 == 0) {
		ret += go(h + 1, r + h / 2, g + h / 2, b) * mul(h, 2);
		ret += go(h + 1, r + h / 2, g, b + h / 2) * mul(h, 2);
		ret += go(h + 1, r, g + h / 2, b + h / 2) * mul(h, 2);
	}
	// 3 color 
	if (h % 3 == 0) {
		ret += go(h + 1, r + h / 3, g + h / 3, b + h / 3) * mul(h, 3);
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> R >> G >> B;
	memset(dp, -1, sizeof(dp));
	make_table();
	cout << go(1, 0, 0, 0) << '\n';
}