[백준] 112727 2xn 타일링 2

https://www.acmicpc.net/problem/11727

이코테 다이나믹 프로그래밍의 바닥공사 예제와 푸는 방식이 같아서 쉽게 할 수 있던 문제였다.

# 112727 : 2xn 타일링 2

import sys
input = sys.stdin.readline

n = int(input())

# dp 테이블 초기화
d = [0] * 1001

d[1] = 1        # 2x1 타일 채우는 방법 1가지
d[2] = 3        # 2x2 타일 채우는 방법 3가지

for i in range(3, n + 1):
    # i - 1 번째 타일까지 채웠다고 가정하면, 2x1 타일 채우는 방법 1가지
    # i - 2 번째 타일까지 채웠다고 가정하면, 2x2 타일 채우는 방법 2가지
        # 2x1 타일 2개로 채우는 방법은 i-1번째까지 채운 타일에서 겹침
    d[i] = (d[i - 1] + 2 * d[i - 2]) % 10007

print(d[n])

Uploaded by Notion2Tistory v1.1.0