[백준 1234] 크리스마스 트리 - JAVA

BOJ Link

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

 

 

풀이 과정

dp[n][r][g][b]을 선언 후, bottom-up dp로 진행한다.

 

n번째 레벨을 채우는 방법은 3가지이다.

 

1. 한 가지 장난감으로 꾸밀 때

n-1의 dp에서 한 장난감을 n개 빼준다.

경우의 수는 이전과 동일하므로, n-1번째 dp와 같다.

 

2. 두 가지 장난감으로 꾸밀 때

해당 경우가 가능하려면, n이 2의 배수여야 한다.

r=2, g=2 두가지 장난감으로 n=4의 레벨을 채운다면,

2개의 자리에 r을 채운 후, 나머지를 g로 채운 것과 같다. (어떤 장난감을 먼저 배치해도 상관 없다.)

r만 채운다면, g는 자동으로 올바르게 채워진다.

따라서, 이는 곧 4C2이다.

 

3. 세 가지 공으로 꾸밀 때

해당 경우가 가능하려면, n이 3의 배수여야 한다.

r=2, g=2, b=2 세가지 장난감 으로 n=6의 레벨을 채운다면,

2개의 자리에 r을 채운 후, 2개의 자리에 g를 채운 후, 나머지를 b로 채운 것과 같다.

r, g만 채운다면, b는 자동으로 올바르게 채워진다.

따라서, 이는 곧 6C4 * 4C2이다.

 

또한,

n=5와 같이 2,3의 배수가 아닌 경우는 한 가지 장난감으로 채워야 한다.

n=6과 같이 2,3의 공배수인 경우는 모든 경우의 수를 더해준다.

 

유의할 점

문제에서 조금 명확하지 않은 조건이 있다. 순서가 다른 것은 다른 경우로 간주한다.

 

헤맨 부분

내가 선언한 배열의 크기는 11*101*101*101*8byte로, 약 90MB인데도 250MB를 넘는 메모리 제한에 걸렸다.

 

런타임 메서드로 조회해보니 500MB정도를 사용하고 있었고, 해당 코드로 구현한 팩토리얼 메서드로 인한 문제였다.

 

public static long fact(int n) {
    return LongStream.rangeClosed(2, n).reduce(1, (l, r) -> l * r);
}

 

 

이후 메모리제이션 하는 코드로 바꿔서 통과했다.

 

제출 코드

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

class Main {

    static long fact[];

    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());

        long[][][][] dp = new long[N + 1][R + 1][G + 1][B + 1];
        fact = new long[N + 1];

        if (R != 0)
            dp[1][R - 1][G][B] = 1;
        if (G != 0)
            dp[1][R][G - 1][B] = 1;
        if (B != 0)
            dp[1][R][G][B - 1] = 1;

        for (int n = 2; n <= N; n++) {
            for (int r = 0; r <= R; r++) {
                for (int g = 0; g <= G; g++) {
                    for (int b = 0; b <= B; b++) {

                        // 한가지 색으로 채울 때
                        if (r - n >= 0)
                            dp[n][r - n][g][b] += dp[n - 1][r][g][b];
                        if (g - n >= 0)
                            dp[n][r][g - n][b] += dp[n - 1][r][g][b];
                        if (b - n >= 0)
                            dp[n][r][g][b - n] += dp[n - 1][r][g][b];

                        // 두가지 색으로 채울 때
                        if (n % 2 == 0) {
                            int div = n / 2;
                            long comb = comb(n, div);
                            boolean rf = r - div >= 0;
                            boolean gf = g - div >= 0;
                            boolean bf = b - div >= 0;
                            if (rf && gf)
                                dp[n][r - div][g - div][b] += dp[n - 1][r][g][b] * comb;
                            if (gf && bf)
                                dp[n][r][g - div][b - div] += dp[n - 1][r][g][b] * comb;
                            if (rf && bf)
                                dp[n][r - div][g][b - div] += dp[n - 1][r][g][b] * comb;
                        }
                        // 세가지 색으로 채울 때
                        if (n % 3 == 0) {
                            int div = n / 3;
                            if (r - div >= 0 && g - div >= 0 && b - div >= 0)
                                dp[n][r - div][g - div][b - div] += dp[n - 1][r][g][b] * comb(n, div) * comb(n - div, div);
                        }
                    }
                }
            }
        }

        long ans = 0;

        for (int r = 0; r <= R; r++) {
            for (int g = 0; g <= G; g++) {
                for (int b = 0; b <= B; b++) {
                    ans += dp[N][r][g][b];
                }
            }
        }

        System.out.println(ans);
    }

    public static long comb(int n, int r) {
        return fact(n) / (fact(n - r) * fact(r));
    }

    public static long fact(int n) {
        if (n == 1) return 1;
        return fact[n] = fact(n - 1) * n;
    }
}