| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 59182 | 35415 | 28379 | 59.279% |
문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
답안
import sys
n = int(sys.stdin.readline())
memo = [1, 3, 0]
for i in range(n-2):
memo[(i+2)%3] = (memo[i%3] * 2 + memo[(i+1)%3]) % 10_007
print(memo[n%3-1])풀이
n이 커짐에 따라 경우의 수가 일정한 규칙에 따라 증가하므로, 이 문제를 DP로 풀어야겠다고 생각했다.
DP로 풀이한 위 답안에서 가장 중요한 부분(점화식)은 다음과 같다.
memo[(i+2)%3] = (memo[i%3] * 2 + memo[(i+1)%3]) % 10_007이 부분이 for 문을 돌면서,
memo[2] = memo[0] * 2 + memo[1] , memo[0] = memo[1] * 2 + memo[2], memo[1] = memo[2] * 2 + memo[3]이 반복된다.
n에서의 경우의 수를 구하기 위해 n-1에서의 경우의 수와 n-2에서의 경우의 수를 이용하는 것인데, 이것이 가능한 이유는 다음과 같다.
n>2을 만족하는 n에 대하여,
n-2에서의 경우의 수, 즉 두 칸이 남아 있을 때 할 수 있는 선택에는 3가지가 있다.
- 1x2 막대기 두 개를 사용하거나(
=모양), - 2x1 막대기 두 개를 사용하거나(
||모양), - 2x2 막대기 한 개(
□모양)를 사용하는 것이다.
또한 n-1에서의 경우의 수, 즉 한 칸이 남아 있을 때 할 수 있는 선택은 유일하다.
- 2x1 막대기 한 개를 사용한다(
|모양)
다만 n-2에서의 경우의 수를 구할 때 2x1 막대기 두 개(||)를 사용하는 것은, 2x1 막대기 한 개(|)를 사용한 뒤 바로 이어 2x1 막대기 한 개(|)를 사용하는 것과 같다.
따라서, 경우의 수를 중복하여 세는 것을 방지하기 위해, n-2에서 두 칸이 남아있을 때 할 수 있는 선택에서 ‘2x1 막대기 두 개를 사용한다’라는 선택지를 없애야 한다.
이 과정을 계속 반복하면, 2x1, 2x2, …, 2xn 크기의 직사각형을 채우는 경우의 수를 차례대로 구할 수 있다.
2x1 크기의 직사각형을 채우는 경우의 수는 한 가지밖에 없고 (2x1 막대기 한 개(|)를 사용하는 경우),
2x2 크기의 직사각형을 채우는 경우의 수는 세 가지이고 (1x2 막대기 두 개를 사용하거나(= 모양), 2x1 막대기 두 개를 사용하거나(|| 모양), 2x2 막대기 한 개(□ 모양)를 사용하는 경우),
2xn 크기의 직사각형을 채우는 경우의 수 = 2x(n-1) 크기의 직사각형을 채우는 경우의 수 + 2 * 2x(n-2) 크기의 직사각형을 채우는 경우의 수
라는 사실을 사용한다면 문제를 풀 수 있게 된다.
이 과정을 반복한 뒤, memo 리스트에서 가장 마지막에 업데이트된 요소가 정답이다.
