[Java] 12996 Acka

문제

문제
BOJ 알고리즘 캠프에 강사로 참여하고 있는 dotorya, kesakiyo, hongjun7은
301호에서 도원결의를 맺고 프로젝트 아이돌 그룹 Acka을 결성했다. 

Acka의 데뷔 앨범에는 총 S개의 곡이 수록될 예정이다. 
각각의 곡은 세 사람중 적어도 한 명이 불러야 한다. 
즉, 어떤 곡은 두 사람이 불러도 되고, 세 사람이 모두 함께 불러도 된다.

세 사람이 녹음해야 하는 곡의 수가 주어질 때, 
앨범을 만들 수 있는 방법의 수를 구하는 프로그램을 작성하시오.

두 앨범 A와 B가 있을 때, 참여한 사람이 다른 곡이 존재한다면, 
두 앨범은 다른 앨범이라고 한다. 

입력
첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다.
(1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S)

출력
첫째 줄에 앨범을 만들 수 있는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

문제 풀이

dp문제 모수가 50정도로 작은 편이다.  경우의 수를 다 구해서 풀이한다.

노래가 S곡이 있을 때 해당 한 곡 씩 배분하다 S <= 0이 되는 시점에 세 사람이 부를 수 있는 곡의 수가 0이 될 때만 카운트를 하면 된다. 

노래를 배분하는 경우의 수는 7가지다. 

 

a 가 부르는 경우

b  가 부르는 경우

c  가 부르는 경우

a b  가 부르는 경우

a c  가 부르는 경우

b c  가 부르는 경우

a b c  가 부르는 경우

 

해당 경우의 수들로 재귀를 돌려서 모든 경우의 수를 구한다.

자바 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class N12996 {
    private static final int[] sing = new int[3];
    private static Long[][][][] dp;
    private static final int mod = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int s = Integer.parseInt(st.nextToken());
        for(int i = 0; i < sing.length; i++){
            sing[i] = Integer.parseInt(st.nextToken());
        }

        dp = new Long[s + 1][sing[0] + 1][sing[1] + 1][sing[2] + 1];

        // dp 리스트를 -1로 초기화
        // -1로 초기화하는 이유는 0으로 초기화한 상태로 돌릴 경우 s의 값이 0인 것이 아직 계산하지 않은 값이 아닌 계산 후에 0이 나온 값이
        // 있을 수 있기 때문이다. 이 경우에는 0을 반환해야하는데 다시 계산하러 로직이 돌아간다.
        for(int i = 0; i <= s; i++){
            for(int j = 0; j <= sing[0]; j++){
                for(int k = 0; k <= sing[1]; k++){
                    Arrays.fill(dp[i][j][k], -1L);
                }
            }
        }
        
        Long result = Singing(s, sing[0], sing[1], sing[2]);

        System.out.println(result);
    }

    public static Long Singing(int s, int a, int b, int c){
        // 모든 노래를 다 불렀을 경우
        if(s <= 0){
            // 모든 인원이 할당량을 다채운 경우
            if(a == 0 && b == 0 && c == 0)
                return 1L;
            // 아닌 경우
            else return 0L;
        }

        // 한 명이라도 값이 음수가 되는 시점에 경우에 수에 포함하지 않는 경우의 수가 된다.
        if(a < 0 || b < 0 || c < 0){
            return 0L;
        }

        // 메모된 값이 있을 경우 호출
        if(dp[s][a][b][c] != -1 ){
            return dp[s][a][b][c];
        }

        long ans = 0;

        // 모든 경우의 수에 대해 확인
        // a 만 부를 경우
        ans += Singing(s - 1, a - 1, b, c);
        // b 만 부를 경우
        ans += Singing(s - 1, a, b - 1, c);
        // c 만 부를 경우
        ans += Singing(s - 1, a, b, c - 1);
        // a와 b가 부를 경우
        ans += Singing(s - 1, a - 1, b - 1, c);
        // a와 c가 부를 경우
        ans += Singing(s - 1, a - 1, b, c - 1);
        // b와 c가 부를 경우
        ans += Singing(s - 1, a, b - 1, c - 1);
        // a b c 모두가 부를 경우
        ans += Singing(s - 1, a - 1, b - 1, c - 1);

        // 결과를 mod로 나눈 나머지를 출력
        ans %= mod;

        // 도출된 값 메모링
        // 다른 재귀 중에 같은 경우에 수에 대해 저장된 값이 있을 때 사용하기 위함
        dp[s][a][b][c] = ans;

        return ans;
    }
}