문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제
(단, 방법의 수를 10007로 나눈 나머지를 출력한다)

입력으로 주어지는 n은 최대 1000까지 가능하다.
즉, 단순 재귀로 풀면 시간 초과가 나기 때문에 DP(동적 계획법) 으로 접근해야 한다.

---

풀이 과정

🧩 점화식 세우기

2×n 직사각형을 채우는 경우의 수를 dp[n]이라고 하자.
dp[n]은 맨 오른쪽 끝에 어떤 타일이 오는지에 따라 경우를 나눌 수 있다.

1️⃣ 세로 타일(2×1) 이 맨 오른쪽에 오는 경우
→ 남은 부분은 2×(n-1)
→ 경우의 수: dp[n-1]

2️⃣ 가로 타일 두 개(1×2 2개) 가 맨 오른쪽에 오는 경우
→ 남은 부분은 2×(n-2)
→ 경우의 수: dp[n-2]

두 경우는 서로 겹치지 않으므로, 이를 더해주면 다음과 같은 점화식이 완성된다.

$dp[n] = dp[n-1] + dp[n-2]$

❌ 내가 처음에 했던 오해
처음에는 이렇게 생각했다.
“2×1 세로 타일(or 1x2 가로 타일 두 개)이 맨 오른쪽에 오는 경우와 맨 왼쪽에 오는 경우 둘 다 세야 하지 않을까?”
$dp[n] = dp[n-1] + 1 + dp[n-2] + 1$ (틀린 점화식이다.)
양쪽 끝을 모두 세려고 하면 같은 타일 배치를 중복으로 세는것과 같다. 따라서 틀린 풀이!

---

코드

1차 시도 : RuntimeError

n = int(input())
dp = [0] * (n + 1)

dp[1] = 1
dp[2] = 2

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

print(dp[n] % 10007)

n = 1일 때 dp의 인덱스는 1까지 밖에 없는데 dp[2] = 2해주면 존재하지 않는 인덱스를 접근한 것이 되어 에러가 발생한다.

✅ 수정된 정답 코드

n이 2 이상일 때만 dp[2]에 접근하도록 수정하였다.

n = int(input())
dp = [0] * (n + 1)

dp[1] = 1
if n >= 2:
    dp[2] = 2

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

print(dp[n] % 10007)

---

배운 점 정리

변수의 범위를 잘 보고, 점화식 초기값을 설정할때 인덱스 범위에 벗어나지 않는지 주의하자.
작은 입력값일수록 “리스트 범위를 벗어나지 않는지”를 항상 확인하자.