[Baekjoon - 12996] Acka

난이도: Gold III

 

태그

• Dynamic Programming

 

풀이

1. \( N \)개의 곡을, 각자 \( a, b, c \)개씩 부르는 경우의 수는?

\( dp_{N, a, b, c} \) = \( N \)개의 곡을 각자 \( a, b, c \)개씩 부르는 경우의 수 라고 해봅시다.

 

초항은 \( dp_{0, 0, 0, 0} = 1 \)이 됩니다.

점화식은, 3명 중 1명 이상이 부르는 아래 7가지 경우의 합을 계산하면 됩니다.

• \( dp_{N-1, a, b, c-1} \)
• \( dp_{N-1, a, b-1, c} \)
• \( dp_{N-1, a, b-1, c-1} \)
• \( dp_{N-1, a-1, b, c} \)
• \( dp_{N-1, a-1, b, c-1} \)
• \( dp_{N-1, a-1, b-1, c} \)
• \( dp_{N-1, a-1, b-1, c-1} \)

 

2. 코드

#include <bits/stdc++.h>
#define endl '\n'
const int PRECISION = 9;
using namespace std;
using ll = long long;
 
const ll mod = 1e9 + 7;
ll dp[52][52][52][52];
 
void Main(){
    int n, a, b, c; cin >> n >> a >> b >> c;
    dp[0][0][0][0] = 1;
    for (int i = 1; i <= n; i++){
        for (int x = 0; x <= a; x++){
            for (int y = 0; y <= b; y++){
                for (int z = 0; z <= c; z++){
                    dp[i][x][y][z] = 0;
                    if (x){ dp[i][x][y][z] += dp[i-1][x-1][y][z]; }
                    if (y){ dp[i][x][y][z] += dp[i-1][x][y-1][z]; }
                    if (z){ dp[i][x][y][z] += dp[i-1][x][y][z-1]; }
                    if (x*y){ dp[i][x][y][z] += dp[i-1][x-1][y-1][z]; }
                    if (x*z){ dp[i][x][y][z] += dp[i-1][x-1][y][z-1]; }
                    if (y*z){ dp[i][x][y][z] += dp[i-1][x][y-1][z-1]; }
                    if (x*y*z){ dp[i][x][y][z] += dp[i-1][x-1][y-1][z-1]; }
                    dp[i][x][y][z] %= mod;
                }
            }
        }
    }
    cout << dp[n][a][b][c];
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
    Main();
}