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를 풀어보자