Table of contents
들어가며
걸린 시간: 24분
처음 문제를 읽고, 사자를 우리에 가두는 경우의 수를 태블릿에 그려 가면서 세어 봤습니다.
세다 보니 이전에 미리 세었던 가지수가 새로 가지수를 셀 때 필요가 하더이다…
그래서 DP로 접근을 했습니다.
키보드에 먼저 손을 올리기 보다는 규칙을 찾고, 점화식을 세우기 시작했습니다.
접근
점화식은 위의 필기에 나온 대로 였습니다.
0은 세로 길이가 n인 우리에서 그 어떤 곳에도 사자를 집어 넣지 않을 때의 경우의 수를 나타내는 dp 테이블의 column입니다.
dp(n, k): 세로 길이가 n인 우리에서 가로 길이가 k인 우리에 사자를 넣는 경우의 수 (단, k가 0이면 세로 길이가 n인 우리들 중에 그 어떤 곳에도 사자를 넣지 않는 경우의 수)
그래서 해당 점화식을 기반으로 구현을 했습니다.
구현
import sys
input = sys.stdin.readline
if __name__ == "__main__":
MOD = 9901
N = int(input().strip())
dp = [[0 for __ in range(3)] for _ in range(N + 1)]
dp[1][0] = dp[1][1] = dp[1][2] = 1
for i in range(2, N + 1):
dp[i][0] = sum(dp[i - 1])
dp[i][0] %= MOD
for j in range(1, 2 + 1):
dp[i][j] = dp[i - 1][0] % MOD + dp[i - 1][3 - j] % MOD
dp[i][j] %= MOD
print(sum(dp[N]) % MOD)
처음에 MOD로 나눠주는 것을 까먹어서, 메모리 초과를 판정 받았습니다.
그제서야 바로 MOD로 나눠주는 게 기억이 나서 나눠주고 AC를 받았습니다.