👉 15990 1,2,3 더하기 5
[정답 코드]
import sys
input = sys.stdin.readline
mod = 1000000009
memo = [[0, 0, 0] for j in range(100001)]
memo[1][0] = 1
memo[2][1] = 1
memo[3][0], memo[3][1], memo[3][2] = 1, 1, 1
for j in range(4, 100001):
memo[j][0] = (memo[j - 1][1] + memo[j - 1][2]) % mod
memo[j][1] = (memo[j - 2][0] + memo[j - 2][2]) % mod
memo[j][2] = (memo[j - 3][0] + memo[j - 3][1]) % mod
t = int(input())
for i in range(t):
n = int(input())
res = 0
for j in range(3):
res += memo[n][j]
print(res % mod)
[풀이]
기본 개념 + 조건 (1, 2, 3이 연속으로 두 번 나올 수 없음)
S(n) = S(n - 1) + S(n - 2) + S(n - 3)
- 3칸 짜리 배열을 만들어 세 가지 경우로 나누어 memoization을 진행한다. (조합의 끝이 1인 경우, 2인 경우, 3인 경우)
- 첫 번째 칸 (index == 0)은 n - 1번째 항에서 1을 더해주는 것을 의미한다. 그러므로, n - 1번째 항에서 끝자리가 2, 3인 경우를 더한 값을 저장해준다.
- 두 번째 칸, 세 번째 칸도 같은 원리로 진행한다.
✔ 시간초과 관리
python의 경우 기본적으로 느리기에 시간 관리를 신경써주어야 한다. 처음 풀 때, test for문 안에서 매번 memo를 초기화하고 계산해주었는데 시간초과가 발생하였다.
test case를 입력 받기 전 모든 결과값을 계산하여 저장해놓은 뒤 진행하자.
[적용 자료구조 및 알고리즘]
- Dynamic Programming
