[#알고리즘/Dynamic Programming/[백준]11726번: 2XN 타일링(python)]

Question

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

Solution

해당 문제에서 n에 따른 타일의 갯수는 아래와 같다.

n = 1 (2 x 1) -> 1
n = 2 (2 x 2) -> 2
n = 3 (2 x 3) -> 3
n = 4 (2 x 4) -> 5
n = 5 (2 x 5) -> 8
...

n이 3이상일 때 f(n) = f(n-1) + f(n-2) 의 식이 적용된다.

Code

n = int(input())

d = [0] * 1001
d[1] = 1
d[2] = 2

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

후기

DP 테이블을 초기화할 때 d = [0] * 1000 이라고 하면 런타임 에러가 발생하여 d = [0] * 1001 로 수정하였더니 해결되었다. 런타임 에러는 주로 잘못된 배열 인덱스 참조가 원인이 된다. DP를 풀 때는 배열 사이즈를 넉넉하게 잡아놓으면 되는데, n의 범위가 1부터 1000까지이므로 1001로 해야 d[0]부터 d[1000]까지 배열이 생성된다. 조심하자 !!