알고스팟 폴리노미노 (poly) 문제 파이썬으로 풀기

세로 단조 폴리노미노의 수를 구하는 문제이다.

이 문제를 풀려면 점화식을 구해서 구현하는 게 가장 좋아 보였는데,

출처: https://sangdo913.tistory.com/41

이 포스팅에서 점화식을 아주 보기에 좋게 구해 놓았으므로, 이를 참고하여 코딩을 했다.

#poly
 
 
def poly(n,d):
    if d == n:
        return 1
    if board[n][d] != -1:
        return board[n][d]
    x = n-d
    ret = 0
    for o in range(1,x+1):
        ret += (o+d-1)*poly(x,o)
        ret %= 10000000
    board[n][d] = ret
    return ret
 
 
board = [[-1 for j in range(101)] for k in range(101)]
case = int(input())
for i in range(case):
    num = int(input())
    result = 0
    for down in range(1,num+1):
        result += poly(num, down)
        result %= 10000000
    print(result)

 

느낀점:

1. 동적계획법은 남이 짜둔 코드만 보면 이해가 잘 가는데, 내가 아무것도 보지 않고 짤때는 더럽게 안된다...