백준 11726번 치킨 2×n 타일링 (Python)

문제

문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

문제 해결 접근

• DP 문제이고 점화식을 찾아내야 하는데 어떡하지? 하면서 엄청 헤맸다.
• 잘못 생각할 때 박혀있던 생각 : 짝수인 경우에는 2의 제곱이고, 홀수인 경우에는 세로 기둥 하나를 어디에 놓을지 경우의 수를 생각해서 곱해주면 될텐데...
• 근데 풀고 나니 오히려 피보나치 수열 문제였다!!!
• 3번째 타일부터는 (1) 바로 앞 타일의 경우의 수가 있고 그 뒤에 새로운 세로 타일 하나를 추가하는 경우와(i-1번째 값을 더해주면 됨), (2) 앞앞 타일의 경우의수가 있고 2x1 타일을 가로로 놓는 경우 (i-2번째 값을 더해주면 됨) 을 생각하면 되었다.
• index 에러가 나지 않게, DP테이블은 입력이 들어올 수 있는 개수만큼 적어주는 게 필요하다.

정답 코드

import sys

n = int(sys.stdin.readline().strip())

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

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

print(array[n]%10007)