NAIAHD

2×n 타일링

출처 : 백준

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

다이나믹 프로그래밍 타일링 문제 풀어보기 (1/2)

DP가 들어가는 문제이다. 

Dynamic programming

나머지는 값이 매우 크질 수 있는 경우를 말한다.

d = [0] * 1001
def dp(n):
    if n in (1,2) :
        return n
    if (d[n]!=0):
        return d[n]
    d[n]= dp(n-1) + dp(n-2)
    return d[n] % 10007

n = 9
dp(n)

RecursionError

검증을 했는데도 불구하고 '틀렸습니다'라고 나와서 좀 당황스러웠다.

혹시나 해서 print()를 추가해보았다.

import sys
sys.setrecursionlimit(10**6)

d = [0] * 1001
def dp(n):
    if n in (1,2) :
        return n
    if (d[n]!=0):
        return d[n]
    d[n]= (dp(n-1) + dp(n-2) ) % 10007
    return d[n] 

n = int(input())
dp(n)