[BOJ] 1234 : 크리스마스 트리(Java)

문제 링크

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

1234번: 크리스마스 트리

---

 

💡 풀이

우선, 전체 색상은 빨간색, 초록색, 파란색으로 3가지 입니다. 따라서, K 레벨에서 장식할 수 있는 경우의 수는 다음과 같이 3가지입니다.

1. 한 가지의 색상만 사용하는 경우
2. 두 가지 색상을 사용하는 경우
3. 세 가지 색상을 사용하는 경우

하지만, 문제 조건에서 각 레벨에 놓으려고 선택한 색의 장난감 수가 같아야 하기 때문에, 두 가지 색상을 사용할 경우는 K가 2의 배수, 세 가지 색상을 사용할 경우는 K가 3의 배수인 경우만 가능합니다. 예를 들어, K = 4 인 경우, [R, G, R, G]와 같이 2가지 색상이 가능하지만, 2의 배수가 아닌 K = 5인 경우 불가능 합니다. 

따라서, 위의 3가지 경우에 따라 분할해 풀이를 진행합니다. 

 

color[N][r][g][b]라는 배열은 N 레벨에서 r, g, b개 남아있을 때 가능한 경우의 수를 의미합니다. 

종료 조건

N, r, g, b에 따라 재귀를 수행하게 되는데, 재귀의 종료 조건은 다음과 같습니다. 

1. r, g, b 중 하나라도 0보다 작아지는 경우 : 더 이상 진행할 수 없기 때문에 0을 반환
2. N <= 0 인 경우 : 모든 레벨에 대해 수행한 경우 개수 1 반환

 // Base Case
if (r < 0 || g < 0 || b < 0) {
    return 0;
}
if (N <= 0) {
    return 1;
}

 

한 가지 색상을 사용하는 경우

한 가지 색상만 사용하는 경우는 다음과 같이 계산될 수 있습니다. 

// 1가지 색상을 사용할 경우
color[N][r][g][b] += solve(N - 1, r - N, g, b);
color[N][r][g][b] += solve(N - 1, r, g - N, b);
color[N][r][g][b] += solve(N - 1, r, g, b - N);

각각, 빨간색을 N개 사용, 초록색을 N개 사용, 파란색을 N개 사용하는 경우에 대해 계산하는 과정입니다. 

 

두 가지 색상을 사용하는 경우

두 가지 색상을 사용하는 경우는 레벨 K에 대해 사용하고자 하는 각 색상이 K/2개 필요합니다. 그리고 [R, G, R, G]와 [R, R, G, G]는 다르게 취급되기 때문에, K에서 한 색상이 들어갈 K/2개의 위치를 선택하는 것을 조합을 이용해 $_KC_{K/2}$ 로 구할 수 있습니다. 이를 이용해 이전 레벨에 이 조합을 곱해주면, 현재 레벨에서 가능한 경우의 수를 구할 수 있습니다. 

 

조합

우선, 조합을 구하는 코드입니다. 최적화를 위해 메모이제이션을 사용했습니다.

static long factorial(int number) {
    if (number == 0 || number == 1) {
        return 1;
    }

    if (dp_factorial[number] != 0) {
        return dp_factorial[number];
    }

    return number * factorial(number - 1);
}

static long combination(int n, int r) {
    if (dp_combination[n][r] != 0) {
        return dp_combination[n][r];
    }

    dp_combination[n][r] = factorial(n) / (factorial(r) * factorial(n - r));
    return dp_combination[n][r];
}

 

다음으로, 두 가지 색상을 사용하는 경우에 대한 코드입니다. 

// 2가지 색상을 사용할 경우 -> N이 2의 배수인 경우만 가능
if (N % 2 == 0) {
    int count = N / 2; // 각 색상을 사용할 개수
    color[N][r][g][b] += solve(N - 1, r - count, g - count, b) * combination(N, count);
    color[N][r][g][b] += solve(N - 1, r, g - count, b - count) * combination(N, count);
    color[N][r][g][b] += solve(N - 1, r - count, g, b - count) * combination(N, count);
}

레벨이 2의 배수이어야 하고, 이전 레벨 값에 현재 레벨에서 가질 수 있는 경우의 수를 곱해주는 방식입니다. 

 

세 가지 색상을 사용하는 경우

마지막으로 세 가지 색상을 사용하는 경우입니다. 각 색상은 K 레벨에서 K/3 개씩 필요합니다. 그리고 K개 중 우선 K/3개가 들어갈 수 있는 자리는 $_KC_{K/3}$이 되고, 남은 자리 중 K/3개가 들어갈 수 있는 경우는 $_{(K-K/3)}C_{K/3}$이 됩니다. 이를 이전 레벨과 곱해주면 현재 레벨에서 경우의 수를 구할 수 있습니다. 

 // 3가지 색상을 사용할 경우 -> N이 3의 배수인 경우만 가능
if (N % 3 == 0) {
    int count = N / 3;
    color[N][r][g][b] += solve(N - 1, r - count, g - count, b - count)
            * combination(N, count) * combination(N - count, count);
}

 

전체 코드

전체적인 코드는 다음과 같습니다. 

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

public class Q1234{
    static long[][][][] color = new long[11][101][101][101];
    static long[] dp_factorial = new long[11];
    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());

        int N = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        int g = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        System.out.println(solve(N, r, g, b));
    }

    static long solve(int N, int r, int g, int b) {
        // Base Case
        if (r < 0 || g < 0 || b < 0) {
            return 0;
        }
        if (N <= 0) {
            return 1;
        }

        // Memoization
        if (color[N][r][g][b] != 0) {
            return color[N][r][g][b];
        }

        // Recursive Case
        // 1가지 색상을 사용할 경우
        color[N][r][g][b] += solve(N - 1, r - N, g, b);
        color[N][r][g][b] += solve(N - 1, r, g - N, b);
        color[N][r][g][b] += solve(N - 1, r, g, b - N);

        // 2가지 색상을 사용할 경우 -> N이 2의 배수인 경우만 가능
        if (N % 2 == 0) {
            int count = N / 2; // 각 색상을 사용할 개수
            color[N][r][g][b] += solve(N - 1, r - count, g - count, b) * combination(N, count);
            color[N][r][g][b] += solve(N - 1, r, g - count, b - count) * combination(N, count);
            color[N][r][g][b] += solve(N - 1, r - count, g, b - count) * combination(N, count);
        }

        // 3가지 색상을 사용할 경우 -> N이 3의 배수인 경우만 가능
        if (N % 3 == 0) {
            int count = N / 3;
            color[N][r][g][b] += solve(N - 1, r - count, g - count, b - count)
                    * combination(N, count) * combination(N - count, count);
        }

        return color[N][r][g][b];
    }

    static long factorial(int number) {
        if (number == 0 || number == 1) {
            return 1;
        }

        if (dp_factorial[number] != 0) {
            return dp_factorial[number];
        }

        return number * factorial(number - 1);
    }

    static long combination(int n, int r) {
        if (dp_combination[n][r] != 0) {
            return dp_combination[n][r];
        }

        dp_combination[n][r] = factorial(n) / (factorial(r) * factorial(n - r));
        return dp_combination[n][r];
    }
}