11726번 : 2xn 타일링

문제보기

파이썬 코드

import sys

n = int(sys.stdin.readline())  # 1 <= n <= 1000

arr = []
arr.append(0)
arr.append(1)
arr.append(2)

i = 3
while i <= n:
    arr.append(arr[i-2] + arr[i-1])
    i += 1

print(arr[n]%10007)

코드 설명

• DP문제이고 문제를 보면 arr[i] = arr[i-2] + arr[i-1]이 성립함
• 효율성을 위해 i=0,1,2 일때의 값에 대한 메모이제이션 실행

포인트

기본적인 수준의 dp 문제. 점화식을 유추하는것도 쉬웠고 이후에는 점화식을 사용하여 재귀만 하면 답이 바로 나옴.