[백준] 11727: 2xn 타일링 2 (Python)

문제📖

풀이🙏

• 타일이 i-1까지 채워져있는 경우 1x2타일 1개를 추가함으로써 i번째 타일을 채울 수 있다.
• 타일이 i-2까지 채워져있는 경우 2x1타일 2개, 2x2 타일 1개를 추가하는 방법 2가지로 i번째 타일을 채울 수 있다.
• 이러한 방식으로 bottom-up을 구성하면 d[i] = d[i-1] + 2 * d[i-2]로 구현 가능하다.

코드💻

n = int(input())

d = [0] * 1001

d[1] = 1 # 2x1 타일을 만드는 방법은 2x1 타일 사용하는 방법
d[2] = 3 # 2x2 타일을 만드는 방법은 1x2 2개 사용, 2x1타일 2개, 2x2 타일 1개 로 총 3가지
for i in range(3, n+1):
    d[i] = (d[i-1] + 2 * d[i-2]) % 10007

print(d[n])