문제

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

풀이

2x$n$ 사이즈의 직사각형을 2x1, 1x2, 2x2 사이즈의 직사각형으로 채우는 문제

점화식부터 만들어 보겠습니다.

n = 1
2x1 하나만 사용 = 1

n = 2
2x1 2개 사용, 1x2 2개 사용, 2x2 1개 사용 = 3

n = 3
(2x1 + 2x1 + 2x1), (2x1 + 1x2 + 1x2), (1x2 + 1x2 + 2x1), (2x1 + 2x2), (2x2 + 2x1) = 5

n = 4
(2x1 + 2x1 + 2x1 + 2x1), (1x2 + 1x2 + 1x2 + 1x2), (2x2 + 2x2), (2x1 + 2x1 + 1x2 + 1x2), (1x2 + 2x1 + 2x1 + 1x2).. = 11

규칙이 보이시나요?
n이 3일 때, 1x2+3 = 5
n이 4일 때, 3x2+5 = 11

즉 n이 i일 때

dp[i] = dp[i-2] * 2 + dp[i-1]

처음에 이를 이용해서

n = int(input())
dp = [0] * 1001 # n의 최대 범위
dp[1] = 1
dp[2] = 3

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

print(dp[n]%10007)

이런 식으로 코드를 작성했는데 계속 틀렸다고 나왔습니다.
여기서 n의 범위가 1부터 1000이기 때문에 1이나 2가 나오면 for문에서 오류가 발생하는 것이였습니다.

여기서 n이 3 이상일 때 for문을 실행하게 만들면 문제가 해결됩니다.

코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 1001
dp[1] = 1
dp[2] = 3

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

print(dp[n]%10007)