[BOJ] 11726번 - 2Xn 타일링

---

문제설명

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

11726번: 2×n 타일링

사고과정

• 예전에 풀어본 이코테의 바닥 공사랑 거의 유사한 유형이다. 단, 주어진 타일 종류가 다르다. 먼저 n = 2,3 될때까지 직접 그려보면서 다이나믹 프로그래밍의 "뒤의 입장에서 생각"하는 마인드로 접근해서 점화식을 잘 세울 수 있었다.
• 단, 몇 번 초반에 자꾸 에러를 받았는데, n = 1일 때 반례를 생각하지 못했다. n = 1 이게 되면 dp 테이블에서 2번 인덱스까지 정의했는데, 초기 array의 인덱스를 범위가 넘어가는 에러가 발생한다. 이를 조심하자.

풀이

n = int(input())
if n == 1:
    print(1 % 10007)
else:
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2

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