[백준 - Python] 11726. 2xn 타일링 (DP)

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

11726번: 2×n 타일링

 

코드

n = int(input())
dp = [0] * (n+2)  # (n+1) 하면 왜 런타임 에러가 나는지 ??

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

print(dp[n] % 10007)

 

이와 비슷한 타일링 문제를

이코테 책으로 DP 공부하면서 풀어봤던 기억 때문에

점화식을 구하는 것은 그렇게 어렵지 않았다.

 

한 가지 의문이었던 점은

DP 테이블에 값을 저장할 때,

인덱스 값이 n값이랑 같게 하기 위해서 n+1의 크기를 갖는 리스트를 선언했는데

제출에서 자꾸 런타임 에러(인덱스 에러)가 났다.

(n+2)로 제출하면 통과가 됐는데,

왜 그런 것인지에 대한 해결을 못해서 스터디원들에게 도움을 구했다.

 

원인은 이랬다.

dp = [0] * (n+1) 인 경우에

n이 1이 들어오면

dp 리스트의 최대 인덱스는 1이 되는데,

그 다다음 줄에서 dp[2] = 2 로 없는 인덱스에 값을 저장하려고 하기 때문에 나는 에러였다!

 

위와 같은 경우를 방지하기 위해서

dp 테이블을 그냥 문제에서 주어지는 최댓값 + 1의 크기로 선언을 하거나

 

아래의 코드와 같이

n = int(input())
dp = [0] * (n + 1)

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

print(dp[n])

 

반복문 안에 조건문으로 나눠서 초기화를 해주는 방법으로 구현을 하면 된다.