[백준 1234번] 크리스마스 트리 (Python3)

import sys
input = sys.stdin.readline
from math import factorial
c = [(0,1),(1,2),(0,2)]

def combination(x,y):
  return factorial(x)//factorial(y)//factorial(x-y)

def DFS(n,cnt):
  global result
  if n == N+1:
    result += cnt
    return
  for i in range(3):
    if RGB[i] >= n:
      RGB[i] -= n
      DFS(n+1,cnt)
      RGB[i] += n
  if not n%2:
    for i,j in c:
      if RGB[i] >= n//2 and RGB[j] >= n//2:
        RGB[i] -= n//2
        RGB[j] -= n//2
        DFS(n+1,cnt*combination(n,n//2))
        RGB[i] += n//2
        RGB[j] += n//2
  if not n%3:
    if RGB[0] >= n//3 and RGB[1] >= n//3 and RGB[2] >= n//3:
      for i in range(3):
        RGB[i] -= n//3
      DFS(n+1,cnt*combination(n,n//3)*combination(n-n//3,n//3))
      for i in range(3):
        RGB[i] += n//3 

N,R,G,B = map(int,input().split())
RGB = [R,G,B]

result = 0
DFS(1,1)
print(result)

DFS + 백트래킹으로 해결하였다.

사실 변수가 3개밖에 없어서 굳이 백트래킹을 사용할 필요 없이 R,G,B를 함수의 변수명에 넣어도 됐었는데, for문으로 좀더 간결하게 짜려다 보니 그렇게 됐다.

 

간력하게 설명하면,

1. 현재의 n에 대해서 R,G,B의 개수가 n보다 큰 경우 cnt*1을 해서 DFS 실행

2. n이 2로 나누어지는 경우 R,G,B 중 n/2보다 더 큰 값 두개를 골라서 DFS 실행, 이때 cnt 값에 combination(n,n/2)를 곱해준다. (왜냐하면 n개의 장식을 서로 다른 색 2개로 채우는 방법의 가짓수가 nCn/2이므로)

3. n이 3으로 나누어지는 경우 R,G,B가 모두 n/3보다 크면 DFS 실행, 이때 cnt 값에 nCn/3 * (n-n/3)Cn/3 을 곱해준다. (이유는 위와 동일)

4. n이 N+1이면 result에 cnt값을 합해주고 최종 결과 출력

 

쉬운 문제였지만 설명이 조금 불친절한 문제였다.

 

 

오늘의 교훈) 백트래킹은 유용하다.