[백준 11726] 2xn 타일링 - 파이썬

백준 11726 - 알고리즘 분류: 다이나믹 프로그래밍

---

 

*풀이과정

Think! 다이나믹 프로그래밍 구현을 위해 재귀함수를 활용한다.

n개의 타일을 채울 수 있는 경우의 수를 f(n)이라고 할 때, f(n) = f(n-1) + f(n-2) 를 떠올리는 것이 핵심이다...

 

f(n) = f(n-1) + f(n-2)

이전 경우의 수에서, 1x2 타일을 추가로 이용하는지, 2x1 타일을 추가로 이용하는지를 기준으로 잡아 생각해보면 된다.

• f(n-1)에서 한 줄이 더 늘어나 2xn 크기의 타일이 되었을 때, 한 줄만 추가되었으므로 1x2 크기의 타일만 사용할 수 있다.
• f(n-2)에서 두 줄이 더 늘어나 2xn 크기의 타일이 되었을 때, 1x2와 2x1 크기의 타일 모두 사용가능하다.
  하지만, 1x2 크기의 타일을 사용하는 경우는 f(n-1)에 포함되므로 제외해야 한다.
  결국 2x1 크기의 타일만 사용할 수 있다.
• 따라서, f(n)은 f(n-1)+f(n-2)와 같다.

1) 메모이제이션을 위하여, 1,001 길이의 리스트를 생성한다. (dp = [0] * 1001)

2) n이 1인 경우와 2인 경우를 저장한다. (dp[1] = 1, dp[2] = 2)

3) for 반복문을 이용하여 dp(n)을 구할 수 있다.

 

n = int(input())
# 메모이제이션을 위한 리스트 생성
dp = [0]*1001
dp[1]=1
dp[2]=2

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


print(dp[n]%10007)