아이디어

• 변수가 4개 있다. (현재 레벨 $n$, 빨강 $r$, 초록 $g$, 파랑 $b$)
  • 4차원 동적 테이블을 사용한다. 여기서는 $f(n, r, g, b)$라 쓰자.
• 경우를 나눠보자.
  • $n$이 1로 나누어 떨어지는 경우(모든 경우): 빨강, 초록, 파랑을 $n$개씩 사용하는 3가지 경우를 고려한다.
  • $n$이 2로 나누어 떨어지는 경우: 추가로 (빨강, 초록), (초록, 파랑), (파랑, 빨강)을 $n \over 2$개씩 사용하는 3가지 경우를 고려한다.
  • $n$이 3으로 나누어 떨어지는 경우: 추가로 모든 색을 $n \over 3$개씩 사용하는 경우를 고려한다.
• 위의 경우에 따라 더한 값은 장난감을 순서 상관 없이 나타내는 방법의 수다.
• 색깔이 $c$개일 때, 장난감을 나열하는 방법의 수는 $t={n \over c}$라 할 때 $\frac{(ct)!}{(t!)^c}$다. 이를 $f_c(t)$라 하자. 아래는 증명이다.
  • 아무 조건 없이 $n$개를 나열하는 경우의 수는 $n! = (ct)!$다.
  • 그러나 같은 색깔끼리는 같은 경우로 취급하므로 같은 색깔 내에서 정렬하는 경우의 수 $t!$을 나누어 준다. 그 작업을 색깔 수 $c$만큼 반복해야 한다.
• 구해야 할 $f_2$, $f_3$ 값의 수가 적으므로 미리 계산해서 하드코딩 해두자.
• 구한 합에다 해당되는 $f_c({n \over c})$ 값을 곱해주면 $f(n, r, g, b)$가 완성된다.
• memoization에 주의하며 $f(N, R, G, B)$를 구하면 정답이다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, R, G, B;
	static long[][][][] memo;	// [n][r][g][b]
	static long[] f2 = {1, 2, 6, 20, 70, 252};	// (2n)!/(n!)^2
	static long[] f3 = {1, 6, 90, 1680};		// (3n)!/(n!)^3
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		R = Integer.parseInt(tk.nextToken());
		G = Integer.parseInt(tk.nextToken());
		B = Integer.parseInt(tk.nextToken());
		
		memo = new long[N+1][R+1][G+1][B+1];
		for (int i=0; i<=N; i++)
		for (int r=0; r<=R; r++)
		for (int g=0; g<=G; g++)
		for (int b=0; b<=B; b++)
			memo[i][r][g][b] = -1;	// uncalculated
		
		System.out.println(f(N, R, G, B));
	}
	
	static long f(int n, int r, int g, int b) {
		if (r < 0 || g < 0 || b < 0) return 0;
		if (n == 0) return 1;
		if (memo[n][r][g][b] != -1) return memo[n][r][g][b];
		long ret = 0;
		ret += f(n-1, r-n, g, b) + f(n-1, r, g-n, b) + f(n-1, r, g, b-n);
		if (n % 2 == 0) {
			int n2 = n / 2;
			ret += f2[n2] * (f(n-1, r-n2, g-n2, b) + f(n-1, r, g-n2, b-n2) + f(n-1, r-n2, g, b-n2));
		}
		if (n % 3 == 0) {
			int n3 = n / 3;
			ret += f3[n3] * f(n-1, r-n3, g-n3, b-n3);
		}
		return memo[n][r][g][b] = ret;
	}
}

메모리 및 시간

• 메모리: 45884 KB
• 시간: 448 ms

리뷰

• 원래 DP는 상향식(tabulation)으로 푸는 편인데, 이번엔 변수가 너무 많아 함수를 만들지 않고서는 예외처리 때문에 도저히 못 배겼기 때문에 하향식으로 풀어보았다.

• 수학하는 놈들, 저리 꺼져라 꺼져!

• 간단한 수학 계산에는 Python IDLE 만큼 편한 게 없다.
  

• 문제 번호 1234네