[백준] 1234번 크리스마스 트리 (gold 2

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

public class Main {
    static int n;
    static int r;
    static int g;
    static int b;
    static long answer = 0;
    static int[] num = new int[11];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.valueOf(st.nextToken());
        r = Integer.valueOf(st.nextToken());
        g = Integer.valueOf(st.nextToken());
        b = Integer.valueOf(st.nextToken());

        //factorial 매번 검사하면 엄청난 시간. 따라서 미리 다 계산
        for (int i = 1; i <= 10; i++) {
            num[i] = factorial(i);
        }
        //총 경우의 수가 대략 1000만 언저리.
        //시간 줄일 수 있는 케이스 다 잡아내고, 백트래킹 돌려도 풀림.
        makeTree(1, 0, 0, 0, 1);
        System.out.println(answer);
    }

    public static void makeTree(int height, int r, int g, int b, long temp) {
        //만약 초과 사용시 리턴
        if (r > Main.r || g > Main.g || b > Main.b) {
            return;
        }
        //최종 높이+1 이면 리턴, 처음을 1로 시작.
        else if (height == n + 1) {
            answer += temp;
            return;
        }
        int i = height;
        if (i % 1 == 0) {
            makeTree(height + 1, r + i, g, b, temp);
            makeTree(height + 1, r, g + i, b, temp);
            makeTree(height + 1, r, g, b + i, temp);
        }
        if (i % 2 == 0) {
            int plus = i / 2;
            long multy = combin(num[i], num[plus], num[plus]);
            makeTree(height + 1, r + plus, g + plus, b, temp * multy);
            makeTree(height + 1, r, g + plus, b + plus, temp * multy);
            makeTree(height + 1, r + plus, g, b + plus, temp * multy);
        }
        if (i % 3 == 0) {
            int plus = i / 3;
            long multy = combin(num[i], num[plus], num[plus], num[plus]);
            makeTree(height + 1, r + plus, g + plus, b + plus, temp * multy);
        }
}

    //팩토리얼 계산
    public static int factorial(int a) {
        int temp = 1;
        for (int i = 1; i <= a; i++) {
            temp *= i;
        }
        return temp;
    }

    //경우의 수 계산, 전체 8개 각각 4개 4개이면 8!/4!4!을 한다.(중복이 있는 순열계산)
    public static long combin(long temp, long div1, long div2) {
        return temp / (div1 * div2);
    }

    public static long combin(long temp, long div1, long div2, long div3) {
        return temp / (div1 * div2 * div3);
    }

}