[백준 2133번] 타일 채우기 (Python3)

import sys
input = sys.stdin.readline
from math import factorial

def DFS(SUM,last):
  global result
  if SUM == N:
    x = factorial(sum(cntlist))
    x //= factorial(cntlist[1])
    x *= 3**cntlist[1]
    for i in range(2,N+1):
      x *= 2**cntlist[i]
      x //= factorial(cntlist[i])
    result += x
  if SUM > N:
    return
  for i in range(last,N+1):
    cntlist[i] += 1
    DFS(SUM+i,i)
    cntlist[i] -= 1

N = int(input())
if N%2:
  print(0)
else:
  N //= 2
  cntlist = [0]*(N+1)
  result = 0
  DFS(0,1)
  print(result)

타일채우기 2 문제가 있길래 경험삼아 풀어보았다.

 

여담으로 N이 30까지밖에 안되기 때문에

result = [0,0,3,0,11,0,41,0,153,0,571,0,2131,0,7953,0,29681,0,110771,0,413403,0,1542841,0,5757961,0,21489003,0,80198051,0,299303201]
print(result[int(input())])

 

이런 코드로도 통과가 가능하다

 

 

오늘의 교훈) 타일채우기 2를 풀어보자