BOJ [Silver III] 2×n 타일링 - 11726

문제 링크

분류

다이나믹 프로그래밍(dp)

문제 설명

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

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

입력

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

출력

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

입력 예시

9

출력 예시

55

내 아이디어

• n이 커지면 오른쪽에 열이 하나 추가되는 것임
• 열이 하나 추가될 때, 아래의 두 가지 규칙으로 경우의 수가 구해짐

1. n-1개의 열을 가진 직사각형에, 2x1 직사각형이 붙는 경우
2. n-1개의 열을 가진 직사각형에, 1x2 직사각형 2개가 붙는 경우

• 방법이 바로 떠올라서 구현하려는데, n-1번째의 경우의 수와 n-2번째의 경우의 수를 더하는 걸 생각하는 데 오래 걸림
• n-1번째 안에 n-2번째가 포함되는 거 아닌가 ... 이러고 있었다
• 그니까 n=4일 때 n=3 사각형이 포함되는데, 그러면 경우의 수 중복이 아녀? 하고 있었던 거
• 규칙 잘 찾고 헛발질 미침 ^,^ ..
• 당연히 옆에 열 하나가 더 붙는 순간 둘은 다른 경우가 되어 버리니까 단순히 둘을 합하면 됨

점화식
$a_i$ : 2 x $i$ 직사각형에서의 경우의 수

$a_i = a_{i-2} + a_{i-1}$

$i$	1	2	3	4	5
$a_i$	1	2	3	5	8

• 위와 같이 표를 그려봤으면 훨씬 $a_{i-2} + a_{i-1}$라는 걸 알 수 있었을텐데!

코드1 : 런타임 에러

n = int(input())
d = [0] * (n+1)
d[1], d[2] = 1, 2
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[-1] % 10007)

• n=1인 경우에 d[2] = 2에서 인덱스 범위 오류남
• 문제 조건에서 입력 값의 범위 잘 확인
• dp 문제에서는 배열 사이즈를 입력 최댓값에 맞춰 넉넉히 잡아놓으면 됨!

코드2 : 맞았습니다

n = int(input())
d = [0] * 1001
d[1] = 1
d[2] = 2
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n] % 10007)

• 사실 배열 사이즈 크게 잡아놓고는 N+1로 잡았을 때처럼 d[-1] % 10007) 해서 한 번 더 틀렸었음 ^,^
  
  

얻은 것

• 입력 조건 확인 또 확인
• dp 문제 배열의 길이 넉넉하게 잡는 게 낫다
• 넉넉하게 잡는다면 출력할 값을 잘 확인해서 작성하기!