[백준11727] 2 x n 타일링 2

문제

---

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

11727번: 2×n 타일링 2

 

생각의 흐름

---

동적 프로그래밍을 사용하여 dp[i]에 2xi를 채우는 경우의 수를 계산하여 넣으면 된다. 점화식은 dp[i]=dp[i-2]*2+dp[i-1]이 되는데 이유는 다음과 같다.

(i-1) 개

2x1

 

(i-2)개

2x1

2x1

 

(i-2)개	1x2
	1x2

 

(i-2)개

2x2

 

위의 그림과 같은 경우가 있는데, 이 중 두번째 경우는 첫번째 경우에 포함이 될 수 있다. 따라서 dp[i-2]*3이 아닌 dp[i-2]*2가 되는 것이다.

 

깨달은 점

---

계속 런타임 에러가 나길래... 원인이 뭔가 했더니 n=1인 경우를 고려해주지 않고 dp[2]를 설정해버리면 안된다! 리스트의 index가 out of range가 되기 때문. 해당 부분은 sys.exit()으로 handle해주었다.

 

코드

---

# 백준11727
import sys

n = int(input())
dp = [0]*(n+1)
if n==1:
    print(1)
    sys.exit()
dp[1], dp[2] = 1, 3
for i in range(3, n+1):
    dp[i] = ((2*dp[i-2])%10007 + (dp[i-1])%10007)%10007
print(dp[n])