BOJ 1234 크리스마스 트리

d[n][r][g][b]=n층의 트리를 만들 때, R이 r개, G가 g개, B가 b개 남아있을 때 트리를 만들 수 있는 경우의 수

문제를 풀기위한 아이디어

n층을 칠할 때 : 1가지 색, 2가지 색(짝수인 경우), 3가지 색(3의 배수인 경우) 가능

일단 문제의 예제를 보면
n이3, r, g, b가 각각 2인 경우
3층에 가능한 경우의 수 : R 1개, G 1개, B 1개 -> 3!/1!/1!/1! -> 3!
2층에 가능한 경우의 수 : R, G / G, B / R, B -> 3가지 경우에 대하여 각 2!

답 : 3! * 2! * 3 = 36

질문 게시판의 nfysh73님의 예제를 참조하면 9층을 R 3, G 3, B 3을 사용하면,
경우의 수 : 9!/3!/3!/3! 이다. 같은 것이 R, G, B 각각 3개씩 있기 때문에 9!을 3!로 3번 나눠준다.
그럼 아래부터 올라가면서 n층에서, 1가지 색, 짝수층이면 2가지 색, 3의 배수 층이면 3가지 색으로 칠하는 경우로 나눠서 가능한 경우와 n-1층을 남은 r, g, b개로 채우는 경우의 수를 곱해준 것들을 다 더한 것이 답이다.

메모리를 조금 쓰고 실행 속도가 빠른 고수님들의 코드를 보니, 배열을 나처럼 잡지 않으시고, r, g, b중 두 가지만 쓰고, 나머지 한 가지는 total-(두 가지의 합)으로 구해서 쓰신다거나.. n을 배열에서 쓰지 않으시고 그냥 parameter로만 넘겨주는 방법도 있었다. 생각해보면 r, g, b는 같으면 n이 다를 수 가 없다...즉 r, g, b만으로도 memoization이 구별되어 되는 것이다. r, g, b가 같은데 n이 다르다는 것은 지금까지 사용한 R, G, B의 개수가 다르다는 것이므로 모순이다.

참조 : 질문 게시판 nfysh73님 질문 글