🔖 https://www.acmicpc.net/problem/1309
✏️ 풀이 과정
📝 접근
- 문제의 규칙을 점화식으로 잘 표현할 수 있다면 간단하게 해결 가능한 문제이다.
- 2 * n 크기의 우리에 대하여 2 * (n - 1) 크기의 우리 아래에 사자를 놓지 않는 경우의 수는
tab[n - 1]이다.
- 2 * n 크기의 우리에 대하여 2 * (n - 1) 크기의 우리 아래에 사자를 놓는 경우의 수는 다시 두 가지 경우로 나누어진다. 2 * (n - 2) 크기의 우리 아래에 사자가 놓여있지 않는 경우, 새로 추가하는 우리에 대하여 어느 방향으로든 사자를 놓을 수 있다. 따라서 해당 경우의 수는 위의 규칙에 따라 2 *
tab[n - 2]이다.
- 2 * (n - 2) 크기의 우리 아래에 사자가 놓여있는 경우에는 한 방향으로만 사자를 놓을 수 있다. 따라서 해당 경우의 수는
tab[n - 1] - tab[n - 2]이다.
- 차례로 구한 모든 경우의 수를 통하여 점화식
tab[n] = 2 * tab[n - 1] + tab[n - 2]을 얻을 수 있다.
✨ 소스 코드
import sys
input = sys.stdin.readline
n = int(input())
tab = [1, 3] + [0] * (n - 1)
for i in range(2, n + 1):
tab[i] = (2 * tab[i - 1] + tab[i - 2]) % 9901
print(tab[-1])
