[python] 11726. 2*n 타일링

 

• 문제

---

 

• 잘못된 풀이

n = int(input())

dp = [0] * n
dp[0] = 1
dp[1] = 2

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

 

해당 문제는 다이나믹 프로그래밍으로 해결할 수 있다.

2*1일 때, 1 / 2*2일 때, 2 / 2*3일 때, 3 / 2*4일 때, 5 / 2*5일 때, 8 으로,

dp[i] = dp[i-1] + dp[i-2]를 만족한다. 

 

하지만 해당 풀이는 dp의 사이즈를 n으로 지정하면서 런타임 오류(IndexError)가 발생하였다.

 

 

• 올바른 풀이

n = int(input())

dp = [0] * 1000
dp[0] = 1
dp[1] = 2

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

 

따라서 IndexError 해결을 위해 n의 유동적인 dp 사이즈를 1000으로 지정해주었다.

 

IndexError를 해결하면서 문제 풀이에 성공하였다.