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

백준 15990번

최종 제출 코드

import sys
input = sys.stdin.readline

MOD = 1000000009

dp = [[0 for i in range(3)] for j in range(100001)]

dp[1] = [1,0,0]
dp[2] = [0,1,0]
dp[3] = [1,1,1]

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

  
n = int(input().rstrip())

for j in range(n):
  number = int(input().rstrip())
  result = (sum(dp[number]))%MOD
  print(result)

코드 출처

.

◼ 점화식을 이용해서 푸는 전형적인 문제

• 1 ⇒ 1
• 2 ⇒ 2
• 3 ⇒ 2+1, 1+2, 3
• 4 ⇒ 1+2+1, 3+1, 1+3
  ...
• n을 문제가 요구하는 대로 구성하는 방법은 n-1에서 마지막 수가 1이 아닌 경우의 수, n-2에서 마지막 수가 2이 아닌 경우의 수, n-3에서 마지막 수가 3이 아닌 경우의 수를 모두 더하는 것이다.
• 배열을 활용하여 각 값들을 저장한다.
  .

◼ 시간초과

• (a + b + c) % mod = (a % mod + b % mod + c % mod) % mod
• 배열에 값을 대입할 때마다 1000000009로 나눈 값을 저장한다.
  .

◼ 동적 알고리즘은 배열만 잘 활용해도 풀 수 있는 문제가 대다수인듯...ㅠㅠ╰(°▽°)╯