백준 15990번 1,2,3 더하기 5

문제 링크

문제 전략

• 가장 마지막(가장 오른쪽)에 더하게 되는 숫자를 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
# 먼저 d[][] 배열을 완성한 뒤에 입력받은 값에 따라 출력을 내보낸다. 
for _ in range(T):
  n = int(sys.stdin.readline())
  print(sum(d[n])%1000000009)