BOJ#1234 크리스마스 트리

BOJ#1234 크리스마스 트리

* 문제

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

* 풀이

dp[N][R][G][B] : 레벨 N에서 장난감이 R, G, B개 남아있을 때 경우의 수

각 레벨에서는 3가지 경우를 탐색합니다. 

1) 장난감을 1가지 종류만 쓰는 경우

2) 장난감을 2가지 종류를 쓰는 경우 (N % 2 == 0일때)

3) 장난감을 3가지 종류를 쓰는 경우 (N % 3 == 0일때)

그리고 각 경우의 수를 구한 뒤 장난감들의 순서도 생각해주어야 합니다.

참고 링크 : https://namu.wiki/w/순열(수학)

3. 같은 것이 있는 경우의 순열(동자 순열)[편집]

n개 중에 r개를 중복없이 순서에 맞게 뽑는데, n개 중에 똑같은 것이 몇개 섞여있을 경우를 말한다. 예를들어 세 개의 문자 $a,a,b$를 일렬로 늘어놓는 순열의 수를 찾아보자. 직접 찾아보면 $aab,aba,baa$의 3가지 경우 밖에 없다. 여기서 좀더 관찰 해보면 3개를 일렬로 늘어놓는 순열의 수는 ${}_3{P}_3=3!=6$, 중복되는 문자는 2개이고, $3=6\mathrm{/}2$이다. 곧, 같은 것이 있을 때는 전체 순열의 수에서 무언가를 나눠주면 된다는 것을 확인할 수가 있다. 그리고 그 무언가는 중복되는 문자를 나열하는 방법의 수, 즉 이 예시에서는 2!이 된다.

중복되는 것이 다른 종류로 여러가지 있을 때도 같은 논리가 성립하며, 이를 수식으로 나타내면 아래와 같다.

$(a_1,a_1,\cdots ,a_1),(a_2,a_2,\cdots ,a_2),\cdots ,(a_n,a_n,\cdots ,a_n)$일 때, 즉 $a_1$이 $p_1$개, $a_2$가 $p_2$개, $\cdots$, $a_n$이 $p_n$개일 때의 순열의 수 $=\frac{(p_1+p_2+\cdots +p_n)!}{p_1!\times p_2!\times \cdots \times p_n!}$

---

* 나의 코드 (Java)

https://github.com/stack07142/BOJ/blob/master/BOJ%231234/src/Main.java

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

public class Main {

    static int N, R, G, B;
    static long[][][][] dp = new long[11][101][101][101];
    static long[][] dp_combination = new long[11][11];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());


        System.out.println(solve(N, R, G, B));

    }

    // return dp[N][R][G][B]
    static long solve(int n, int r, int g, int b) {

        if (r < 0 || g < 0 || b < 0) return 0;
        if (n <= 0) return 1;

        // Memoization
        if (dp[n][r][g][b] != 0) return dp[n][r][g][b];

        // 레벨 N에서, 3가지 경우 탐색
        // 1가지 색만 쓰는 경우
        dp[n][r][g][b] += solve(n - 1, r - n, g, b);
        dp[n][r][g][b] += solve(n - 1, r, g - n, b);
        dp[n][r][g][b] += solve(n - 1, r, g, b - n);

        // 2가지 색만 쓰는 경우
        if (n % 2 == 0) {

            int piece = n / 2;
            long combination = getCombination(n, piece, 2);

            dp[n][r][g][b] += combination * solve(n - 1, r - piece, g - piece, b);
            dp[n][r][g][b] += combination * solve(n - 1, r, g - piece, b - piece);
            dp[n][r][g][b] += combination * solve(n - 1, r - piece, g, b - piece);
        }

        // 3가지 색만 쓰는 경우
        if (n % 3 == 0) {

            int piece = n / 3;
            long combination = getCombination(n, piece, 3);

            dp[n][r][g][b] += combination * solve(n - 1, r - piece, g - piece, b - piece);
        }

        return dp[n][r][g][b];
    }

    static long getCombination(int n, int piece, int k) {

        // memoization
        if (dp_combination[n][piece] != 0) return dp_combination[n][piece];

        long ret = 1L;

        for (int i = 1; i <= n; i++) {

            ret *= i;
        }

        for (int i = 0; i < k; i++) {

            for (int j = 1; j <= piece; j++) {

                ret /= j;
            }
        }

        return dp_combination[n][piece] = ret;
    }
}