[백준/파이썬] 9095 1, 2, 3 더하기

#문제링크

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

#나의풀이

import sys

if __name__ == '__main__':
    T = int(sys.stdin.readline())
    dp = [0] * 12
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

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

    for _ in range(T):
        number = int(sys.stdin.readline())
        print(dp[number])

#해설

계단오르기와 비슷한 전형적인 DP문제가 아닐까 싶다.

4를 구한다고 했을때 4를 쪼갠다고 생각하면 1 + dp[3], 2+ dp[2], 3 + dp[1]으로 3가지 방법으로 나눌수가 있는데 이를 경우의 수로 구면 dp[3] + dp[2] + dp[1]만 더해주면 되므로 점화식이 dp[i-3] + dp[i-2] + dp[i-1]로 되는걸 확인할 수 있다.