[백준] 15988번(1, 2, 3 더하기 3)

백준 15988번

최종 제출 코드

MOD = 1000000009

dp = [0]*(1000001)
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, len(dp)):
  dp[i] = (dp[i-3]%MOD + dp[i-2]%MOD + dp[i-1]%MOD)%MOD

N = int(input())

for k in range(N):
  n = int(input())
  print(dp[n])

◼ 전형적인 점화식을 세워 푸는 문제

• n=1, (1)
• n=2, (1,1), (2)
• n=3, (1,1,1), (1,2), (2,1), (3)
• n=4
  ◻ n=1인 케이스 뒤에 3을 붙임
  ◻ n=2인 케이스 뒤에 2을 붙임
  ◻ n=3인 케이스 뒤에 1을 붙임
• ...
  ⇒ i번째 원소의 값 = i-3번째 원소값 + i-2번째 원소값 + i-1번째 원소값