문제 링크
문제 전략
- 가장 마지막(가장 오른쪽)에 더하게 되는 숫자를 1,2,3 일때의 경우를 각각 나누어
점화식
을 세운다.
- d[i][j] : i를 만들기 위해 가장 마지막에 j가 오면서 가능한 1,2,3의 조합의 갯수라고 할때 조건에 맞는 점화식을 세운다.
- 1,2,3일때 점화식을 세우고 범위에 따라 예외조건을 작성
알고리즘 종류
import sys
limit = 100000
T = int(sys.stdin.readline())
d = [[0]*4 for _ in range(0,limit+1)]
for i in range(1,limit+1):
if i>1:
d[i][1] = d[i-1][2] + d[i-1][3]
if i ==1:
d[i][1] = 1
if i >2:
d[i][2] = d[i-2][1] + d[i-2][3]
if i ==2:
d[i][2] = 1
if i>3:
d[i][3] = d[i-3][1] + d[i-3][2]
if i==3:
d[i][3] = 1
d[i][1] %= 1000000009
d[i][2] %= 1000000009
d[i][3] %= 1000000009
for _ in range(T):
n = int(sys.stdin.readline())
print(sum(d[n])%1000000009)