[백준] 11726 - 2xn 타일링

아이데이션

전형적인 다이나믹 프로그래밍 문제이다!!

n = 1일 때부터 블럭을 차근차근 쌓아 나가면서, 두가지 갈래를 선택하게 된다

1. n - 1까지 쌓은 상태에서 2x1 타일을 하나 쌓기

2. n - 2까지 쌓은 상태에서 2x1 타일을 두개 쌓기

그럼 현재의 경우의 수는? 1과 2를 더한 값이 된다!!

풀이

 

n = int(input())

cache = [1] * (n + 1)

for i in range(2, n + 1, 1):
    cache[i] = cache[i - 2] + cache[i - 1]

print(cache[n] % 10007)