백준 11726번 : 2xn 타일링 (Python)

문제 : www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

풀이

 

dp에 2x1부터 경우의 수를 입력한 뒤 입력된 수를 참고하여 다음 2xn 크기의 타일링을 계산한다.

현재 주어진 타일로 겹치지 않게 가장 작게 사각형을 채우는 방법은

①세로 타일 하나로 2x1 만들기  ②가로 타일 두개로 2x2 만들기 이다.

ex) 세로 타일 두개로 2x2를 만드는 경우는 ①의 경우에 속하므로 겹치는 경우이다.

따라서 2xn 타일링 경우의 수는 [ 2x(n-1)에 ①을 붙이는 경우 + 2x(n-2)에 ②를 붙이는 경우 ]이다.

 

n = int(input())

dp = [0,1,2]

for i in range(3,n+1):
    dp.append((dp[i-2] + dp[i-1])%10007)

print(dp[n])