11727 2xn 타일링2

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

N = int(input())
dp_table = [0] * 1000
dp_table[0] = 1
dp_table[1] = 3
for i in range(2,N):
    dp_table[i] = (dp_table[i-1]+dp_table[i-2]*2)%10007
print(dp_table[-1])

3. 문제 풀이

이 문제는 전형적인 타일링 문제이다. 아주 대표적인 문제라 풀이 자체는 어렵지 않았으나, 내 견해를 간단히 적고자한다. 점화식을 구성하기위해 그림을 그리다보면, 2가지 점화식을 나뉘게 되는데, 타일의 너비가 2짜리를 붙일 땐 i-2번째 dp table에서 값을 가져오게 된다. 근데, 이때 2x1짜리 타일 2개를 붙여서 2x2짜리 타일을 만들 수도 있다. 하지만 이것을 사용하면 안된다. 왜냐하면 이것은 2x1짜리 타일을 dp table의 i-1번째에 붙일 때 나올 수 있기 때문이다. 근데 이걸 이렇게 생각하지 않고 2x2짜리 타일을 붙일 경우엔 꼭 2x2타일로만 붙일 수 있는 경우만을 넣으면 어떨까 생각했다. 그렇게되면 겹치는 경우가 안생길 것이라고 생각하기 때문이다.