[백준 1234] 크리스마스 트리 (C++)

1234번: 크리스마스 트리

 

레벨이 최대 10이므로 1 + ... + 10 = 55 이다.

따라서 한가지 색을 최대 55개까지만 사용할 수 있다. -> 배열의 크기가 [11][60][60][60]인 이유

 

cache 배열은 [현재 층][빨간색을 사용한 횟수][초록색을 사용한 횟수][파랑색을 사용한 횟수] = 경우의 수

 

기저조건은 재귀를 돌면서 현재 층이 N을 넘기면 해당 경우가 있다는 뜻으로 1을 반환하도록 했다.

 

각 층마다 사용된 색의 개수가 모두 같아야 하고, 각 층마다 색깔에 따라서 순열이 적용되므로 같은것이 포함된 순열의 경우의 수를 계산해 준다.

 

각 층마다 1가지 색만을 사용하는 경우 + 2가지 색깔을 사용하는 경우 + 3가지 모두 사용하는 경우를 더해서 현재 cache[][][][]값으로 정해준다.

 

#include <iostream>
#include <cstring>
 
typedef long long ll;
using namespace std;
 
int N, R, G, B;
 
ll cache[11][60][60][60];
int fact[11];
 
int getFacto(int n){
    if(n == 0 || n == 1) return 1;
    if(fact[n]) return fact[n];
    return fact[n] = n * getFacto(n-1);
}
 
int numCase(int facto, int r, int g, int b){
    return facto / getFacto(r) / getFacto(g) / getFacto(b);
}
 
ll dfs(int lv, int r, int g, int b){
    if(lv > N) return 1;
    
    ll &ret = cache[lv][r][g][b];
    if(ret != -1) return ret;
    
    ret = 0;
    
    // 1가지 색 사용
    if(R - r >= lv) ret += dfs(lv+1, r+lv, g, b);
    if(G - g >= lv) ret += dfs(lv+1, r, g+lv, b);
    if(B - b >= lv) ret += dfs(lv+1, r, g, b+lv);
    
    // 2가지 색 사용
    if(lv % 2 == 0){
        if(R - r >= lv/2 && G - g >= lv/2){
            ret += (numCase(getFacto(lv), lv/2, lv/2, 0) * dfs(lv+1, r+lv/2, g+lv/2, b));
        }
        if(B - b >= lv/2 && G - g >= lv/2) {
            ret += (numCase(getFacto(lv), 0, lv/2, lv/2) * dfs(lv+1, r, g+lv/2, b+lv/2));
        }
        if(R - r >= lv/2 && B - b >= lv/2){
            ret += (numCase(getFacto(lv), lv/2, 0, lv/2) * dfs(lv+1, r+lv/2, g, b+lv/2));
        }
    }
    
    // 3가지 색 사용
    if(lv % 3 == 0 && R - r >= lv/3 && G - g >= lv/3 && B - b >= lv/3){
        ret += (numCase(getFacto(lv), lv/3, lv/3, lv/3) * dfs(lv+1, r+lv/3, g+lv/3, b+lv/3));
    }
    
    return ret;
}
 
int main(){
    cin >> N >> R >> G >> B;
    memset(cache, -1, sizeof(cache));
    cout << dfs(1, 0, 0, 0);
    
    return 0;
}