크리스마스 트리 C++ - 백준 1234

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

DP 문제.

"같은 것이 있는 순열"을 복습하게 해준 문제이다.

PS할 때 조합론 역시 중요하다는 것을 다시 한번 깨닫게 해준 문제.

문제 접근

$DP[i][j][k]$ 를 빨강 $i$, 초록 $j$, 파랑 $k$개를 사용했을 때의

경우의 수라고 하자.

추가로 현재 층을 $d$ 라고 할 때

$DP[i][j][k]$에는 현재 층이 짝수라면 $(i-d/2,j-d/2,k),$

$(i-d/2,j,k-d/2),(i,j-d/2,k-d/2)$에서 올 수 있고

현재 층이 3의 배수라면

$(i-d/3,j-d/3,k-d/3)$에서 올 수 있다.

그런데 이때 색 별로 자리를 바꾸는 경우도 생각해주어야 한다.

이 경우의 수는 고등학교 때

"같은 것이 있는 순열" 한 번씩 문제를 풀어봤다면

익숙할 것이다.

서로 다른 물체를 일렬로 나열하는 경우의 수는 $n!$이고,

$a$ 를 $n$개 $b$ 를 $m$개 가지고 있을 때 나열하는 경우의 수는

$a$와 $b$ 모두를 다른 물체로 고려하고 나열한 경우에서

$a$ 를 $n$ 개 나열하는 경우와 $b$ 를 $m$ 개 나열하는 경우를

제외해주면 된다.

따라서 $\frac {(n+m)!}{n!m!}$이 된다.

이것을 점화식에 적용하면

$DP[i][j][k]=(d/2개씩\;사용해\;오는\;경우)\times\frac {d!}{\frac d2!\frac d2!}$

$+(d/3개씩\;사용해\;오는\;경우)\times\frac {d!}{\frac d3!\frac d3!\frac d3!}$ 가 된다.

이를 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll fact[11];
ll dp[56][56][56];
ll n,res=0;
int r,g,b;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    fact[1]=1;
    for(int i=2;i<11;i++) fact[i]=fact[i-1]*i;
    vector<int> f; for(int i=1;i<11;i++) f.push_back(i*(i+1)/2);
    cin >> n >> r >> g >> b;
    r=min(r,55);
    g=min(g,55);
    b=min(b,55);
    dp[0][0][0]=1;
    for(int i=0;i<=r;i++){
        for(int j=0;j<=g;j++){
            for(int k=0;k<=b;k++){
                auto it=lower_bound(f.begin(),f.end(),i+j+k);
                if(it==f.end() || *it!=i+j+k) continue;
                ll d=it-f.begin()+1;
                if(i>=d) dp[i][j][k]+=dp[i-d][j][k];
                if(j>=d) dp[i][j][k]+=dp[i][j-d][k];
                if(k>=d) dp[i][j][k]+=dp[i][j][k-d];
                if(d%2==0 && i>=d/2 && j>=d/2) dp[i][j][k]+=fact[d]/fact[d/2]/fact[d/2]*dp[i-d/2][j-d/2][k];
                if(d%2==0 && j>=d/2 && k>=d/2) dp[i][j][k]+=fact[d]/fact[d/2]/fact[d/2]*dp[i][j-d/2][k-d/2];
                if(d%2==0 && i>=d/2 && k>=d/2) dp[i][j][k]+=fact[d]/fact[d/2]/fact[d/2]*dp[i-d/2][j][k-d/2];
                if(d%3==0 && i>=d/3 && j>=d/3 && k>=d/3) dp[i][j][k]+=fact[d]/fact[d/3]/fact[d/3]/fact[d/3]*dp[i-d/3][j-d/3][k-d/3];
                if(d==n) res+=dp[i][j][k];
            }
        }
    }
    cout << res;
    return 0;
}