[알고리즘][X] 크리스마스 트리

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

 

import java.io.*;
import java.util.*;

public class solution1234 {
	
	static int N;
	static int red;
	static int green;
	static int blue;
	static long[][][][] dp;
	static int[] fact;
	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());
		red = Integer.parseInt(st.nextToken());
		green = Integer.parseInt(st.nextToken());
		blue = Integer.parseInt(st.nextToken());
		dp = new long[red + 1][green + 1][blue + 1][N];
		fact = new int[3628801];

		StringBuilder sb = new StringBuilder();
		/*
		if (N * (N + 1) / 2 != (red + green + blue)) {
			System.out.println(0);
			return;
		}
		*/
		int[] toys = new int[3];
		toys[0] = red;
		toys[1] = green;
		toys[2] = blue;
		long ans = find_ans(toys, 0);

		sb.append(ans);
		System.out.println(sb);
	}

	public static long find_ans(int[] toys, int depth) {
		if (depth == N) {
			return 1;
		}
		
		if (dp[toys[0]][toys[1]][toys[2]][depth] != 0) {
			return dp[toys[0]][toys[1]][toys[2]][depth];
		}
		
		long ans = 0;
		int level = depth + 1;
		// 1
		for (int i = 0; i < 3; i++) {
			int[] temp_toys = Arrays.copyOf(toys, toys.length);
			if (toys[i] >= level) {
				temp_toys[i] -= level;
				ans += find_ans(temp_toys, depth + 1);
			}
		}
		// 2
		if (level % 2 == 0) {
			for (int i = 0; i < 3; i++) {
				int criteria = level / 2;
				int[] temp_toys = Arrays.copyOf(toys, toys.length);
				boolean flag = false;
				for (int j = 0; j < 3; j++) {
					if (i == j) {
						continue;
					}
					
					if (temp_toys[j] >= criteria) {
						temp_toys[j] -= criteria;
					} else {
						flag = true;
						break;
					}
				}
				if (!flag) {
					ans += find_ans(temp_toys, depth + 1) * factorial(level) / (factorial(level / 2) * factorial(level / 2));
				}
			}
		}
		// 3	
		if (level % 3 == 0) {
			int criteria = level / 3;
			int[] temp_toys = Arrays.copyOf(toys, toys.length);
			boolean flag = false;
			for (int i = 0; i < 3; i++) {
				if (temp_toys[i] >= criteria) {
					temp_toys[i] -= criteria;
				} else {
					flag = true;
					break;
				}
			}
			if (!flag) {
				ans += find_ans(temp_toys, depth + 1) * factorial(level) / (factorial(level / 3) * factorial(level / 3) * factorial(level / 3));

			}
		}
		
		dp[toys[0]][toys[1]][toys[2]][depth] = ans;
	       	return ans;	
	}

	public static int factorial(int N) {
		if (fact[N] != 0) {
			return fact[N];
		}
		if (N == 1) {
			return 1;
		}
		
		fact[N] = N * factorial(N - 1);
		return fact[N];
	}
}

나의 풀이

- dp + 재귀

- 주석 친 부분을 했다가 예외를 놓쳤다. 모든 레벨에 쌓고 나서도 장난감이 남을 수도 있다.

- 2^63 - 1보다 작다고 해서 문득 int를 생각했다. 파이썬과 헷갈린 것도 있고 int가 얼마만큼 커버하는지도 잊었었다. int는 4byte이기 때문에 절댓값으로 2 ^ 31 - 1만큼 가능하다.