백준 알고리즘 11726번 2×n 타일링(python)

기본적인 다이나믹 프로그래밍 문제이다. 두 가지 경우만 고려하면 쉽게 풀 수 있다.

1. 2*(n-1) -> 2*n: 타일이 한 개 들어가는 경우밖에 없기 때문에 2*(n-1) 크기의 직사각형에 타일을 배치하는 방법의 수만큼만 더해주면 된다.

2. 2*(n-2) -> 2*n: 타일이 두 개가 들어갈 수 있는데 타일을 세워서 배치하는 경우는 1번과 겹치기 때문에 넘어가고,

가로로 두 개 배치되는 경우만큼만 더해주면 된다.

정리하면 dp[i] = dp[i-2] + dp[i-1], (i > 2)과 같다.

n = int(input())
dp = [0, 1, 2]
for i in range(3, n+1):
    dp.append(dp[i-2]+dp[i-1])
print(dp[n])