[백준 15989번] 1, 2, 3 더하기 4

import sys

input = sys.stdin.readline

t = int(input())

dp = [1]*10001

for i in range(2,10001):
    dp[i] += dp[i-2]

for i in range(3,10001):
    dp[i] += dp[i-3]

for i in range(t):
    print(dp[int(input())])

 

이번 문제는 주어진 숫자를 1, 2, 3을 사용하여 만들 수 있는 경우의 수를 구하는 문제이다.

 

1부터 10까지의 케이스를 구하다보니 패턴이 존재할 것 같다는 예감이 들었고, DP문제라는 것을 감으로 알 수 있었다.

 

하지만 점화식을 찾는 것이 너무 어려워서 다른 블로그를 참고하였다.

 

먼저 모든 숫자는 1로만 채우는 방법이 존재하기 때문에 DP테이블을 1로 초기화시켜주고, 모든 항은 자신보다 2칸과 3칸 전에 있는 항을 더해준 것과 같기 때문에 위와 같은 점화식을 적용할 수 있다.