[백준 12996번] Acka (C++)

문제링크 : https://www.acmicpc.net/problem/12996

12996번: Acka

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

#define MOD 1000000007

int S, s1, s2, s3;
ll dp[51][51][51][51];

ll func(int S, int s1, int s2, int s3)
{
    if (s1 < 0 || s2 < 0 || s3 < 0) return 0;
    if (S == 0) return (s1 == 0 && s2 == 0 && s3 == 0) ? 1 : 0;

    if (dp[S][s1][s2][s3] != -1) return dp[S][s1][s2][s3];    //메모이제이션

    dp[S][s1][s2][s3] = 0;

    dp[S][s1][s2][s3] += func(S - 1, s1 - 1, s2, s3);         //a만 부를 경우
	dp[S][s1][s2][s3] += func(S - 1, s1, s2 - 1, s3);         //b만 부를 경우
	dp[S][s1][s2][s3] += func(S - 1, s1, s2, s3 - 1);         //c만 부를 경우
	dp[S][s1][s2][s3] += func(S - 1, s1 - 1, s2 - 1, s3);     //a,b가 부를 경우
	dp[S][s1][s2][s3] += func(S - 1, s1 - 1, s2, s3 - 1);     //a,c가 부를 경우
	dp[S][s1][s2][s3] += func(S - 1, s1, s2 - 1, s3 - 1);     //b,c가 부를 경우
	dp[S][s1][s2][s3] += func(S - 1, s1 - 1, s2 - 1, s3 - 1); //a,b,c가 부를 경우
	dp[S][s1][s2][s3] %= MOD;

	return dp[S][s1][s2][s3];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    memset(dp, -1, sizeof(dp));
    cin >> S >> s1 >> s2 >> s3;
    cout << func(S, s1, s2, s3);

    return 0;
}

dp문제다.

dp 배열을 dp[S][s1][s2][s3]으로 선언하고, 각각의 개수가 줄어들때 마다 -1을 해줘서 표시한다.

(ex : s1만 불렀을 경어 dp[S-1][s1-1][s2][s3])

곡의 갯수가 0일때, 각각의 가수들이 불러야 할 곡을 전부 불렀다면 맞는 케이스이므로 1을 리턴한다.

 

-1을 해주기에 가수들이 부른 곡이 음수로 갈때도 있는데, 이렇게 되면 필요없다고 생각하여 음수일때 바로 return 0으로 처리했다.

계산과정을 줄이기 위해 이렇게 했는데 큰 의미는 없는 듯 하다.