boj 12996 Acka

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

12996번: Acka

N곡을 세 사람이 나눠서 불러 앨범을 완성해야 합니다.

정확히 N곡을 불러야하며, 세 사람의 기회가 모두 소진되어야 합니다.

 

그러면 경우의 수를 얻는 조건은 N이 0이되면서 세 사람의 기회가 모두 0이 되는 경우에만 1을 추가합니다.

dp[N][x][y][z]: N곡이 남았고, 세 사람의 기회가 x, y, z만큼 있을 때 앨범을 완성할 수 있는 경우의 수

 

한 곡에 대해 부를 수 있는 경우는 아래와 같습니다.

1. 세 사람 중 적어도 한 명 이상이 불러야 한다.
2. 세 사람 모두가 한 곡을 불러도 된다.
3. 세 사람 중 두 사람이 한 곡을 불러도 된다.
4. 세 사람 중 한 사람이 한 곡을 불러도 된다.

이 문제는 간단하게 위의 경우를 하나씩 모두 구해주시면 되겠습니다.

경우의 수를 더하면서 % MOD 연산을 해주도록 합시다.

 

 

#include <iostream>
#include <cstring>
#define MAX 51
#define MOD 1000000007
using namespace std;
 
int dp[MAX][MAX][MAX][MAX];
int N, x, y, z;
 
int solve(int n, int a, int b, int c) {
    if (!n) {
        return !a && !b && !c;
    }
    
    int& ret = dp[n][a][b][c];
    if (ret != -1) return ret;
    ret = 0;
 
    if (a && b && c) {
        ret = (ret + solve(n - 1, a - 1, b - 1, c - 1)) % MOD;
    }
 
    if (a && b) {
        ret = (ret + solve(n - 1, a - 1, b - 1, c)) % MOD;
    }
    if (a && c) {
        ret = (ret + solve(n - 1, a - 1, b, c - 1)) % MOD;
    }
    if (b && c) {
        ret = (ret + solve(n - 1, a, b - 1, c - 1)) % MOD;
    }
 
    if (a) {
        ret = (ret + solve(n - 1, a - 1, b, c)) % MOD;
    }
    if (b) {
        ret = (ret + solve(n - 1, a, b - 1, c)) % MOD;
    }
    if (c) {
        ret = (ret + solve(n - 1, a, b, c - 1)) % MOD;
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    cout << solve(N, x, y, z) << '\n';
}
 
void input() {
    cin >> N >> x >> y >> z;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}