BOJ 11726 2×n 타일링 python

개인적으로는 BOJ 9095 1,2,3 더하기 문제랑 비슷한 느낌이 있었다. 전형적인 dp 문제였다.

BOJ 9095 1,2,3 더하기 python

기

2n 타일을 채우기 위해 2(n-1) 타일을 채우는 방법의 수 등을 이용할 수 있을 것 같다는 생각이 들었고, 점화식을 세우기 시작했다.

승

점화식을 세우기 위해서는 2*(n-2) 타일을 채우는 방법의 수 까지만 고려하면 된다고 생각했다. 타일의 크기가 21이기 때문에, (n-2)번 타일을 채우면 방법이 있으면 그 뒤 남은 22 타일을 어떻게 채울 지 고민하는 문제이기 때문이다.

전

그러면 (n-2)번째 이후의 타일을 어떻게 채우느냐가 관건이다.

(n-2)번째 이후의 2*2 타일을 채우기 위해선 , 가로로 두 개의 타일을 두는 방법과 세로로 두 개의 타일을 두는 방법이 있다.

(n-1)번째 이후의 2*1 타일을 채우기 위해선, 세로로 한 개의 타일을 두는 방법이 있다.

어 그러면, An = 2 * An-2 + An-1 아니야? 라고 생각할 수 있는데,

세로로 두 개의 타일을 두는 방법은 사실 An-1의 방법에 포함된다!!(이전 한 개의 타일이 세로였을 경우도 포함하고 있기 때문에, 결론적으로 마지막 두 개의 타일이 세로로 놓여진 경우도 포함이다)

따라서, 점화식은 An = An-2 + An-1 으로 작성된다.

결

약간의 함정이 있었지만 점화식을 떠올리는 게 관건이었던, 구현이 몹시 쉬운 문제였다. 메모리도 일차원 리스트로 간단하게 만들어버리면 된다.

---

코드

x = int(input())

d = [0] * (x+2)
d[1] = 1
d[2] = 2

if x >= 3:
    for i in range(3, x+1):
        d[i] = d[i-1] + d[i-2]

print(d[x] % 10007)