백준Python : 2*N 타일링 2

동적계획법을 사용한다

2 * N 번째 타일링을 할 경우, 다음 3가지 경우의 수가 존재한다.

1) 2 ( N - 1) 까지의 타일링 + 끝에 1 짜리 타일링
2) 2 ( N - 2) 까지의 타일링 + 끝에 22 짜리 타일링
3) 2 ( N - 2) 까지의 타일링 + 끝에 가로 1*2 짜리 2개 타일링

dy[n]를,
2 * n 까지의 타일링 갯수.라고 하면,

dy[n] = dy[n-1] + dy[n-2] * 2

질문 !

다른 경우의 수가 존재하지 않을까 ?

예를 들어
" 4) 2 * ( N - 2 ) 까지의 타일링을 한 이후, 1세로 타일링을 2개 "

안된다.
왜냐하면, 이것은 1) 경우에 포함되기 때문이다....?

예를 들어, 4개의 타일링이 있다고 해보자

4) 라는 새로운 경우는 곳,
d[2] + 1짜리 세로타일링 2개.

그런데 자세히 보면,
이것은 이미 d[3]에 포함되어 있다

d[2] + 세로타일링 1개 => d[3] 에 포함.

그런데 d[4] = d[2] + 세로타일링 2개 , 까지 count하면

"d[2] + 세로1개 타일링"이 중복 counting 되는 것이다.

즉, 이미 d[3] 은, d[2] + 세로 타일링.의 경우를 포함하고 있는 것 .

그런데

d[4]
= d[3] + 세로 짜리 1개 타일링 ( + )
= d[2] + 세로 짜리 2개 타일링

이렇게 하게 되면,
사실 d[3] + 세로짜리 1개 타일링. 에
d[2] + 세로짜리 2개 타일링. 이 포함되는 것이다.

이러한 중복을 방지하기 위해
4) 2 * ( N - 2 ) 까지의 타일링을 한 이후, 1세로 타일링을 2개 . 는 제외해주는 것이다.

1번째 코드

import sys
sys.setrecursionlimit(100000)

n = int(input())

arr = [0] * ( n + 1 )
arr[1] = 1
arr[2] = 3

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

print(arr[n] % 10,007)

이렇게 runtime error 가 나는 이유는,
n = 1일때
arr[2] = 3 이라고 설정을 해주기 때문이다. 실제 arr[1]까지만 공간이 있는데도 불구하고 !

2번째 코드

import sys
sys.setrecursionlimit(100000)


n = int(sys.stdin.readline())
d = [ 0, 1, 3 ]
for i in range(3, n + 1 ):
    d.append((d[i-1] + d[i-2] * 2) % 10007)

print(d[n])