[백준] 9095 '1, 2, 3 더하기' 파이썬(python)

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

9095번: 1, 2, 3 더하기

T = int(input())   

nums = []    # 수들을 담기 위한 리스트

dp = [0] * 11    # DP 테이블. 최대 11이므로 11까지 받는다.
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, 11) :    # 귀납법으로 규칙을 찾다보면 아래와 같은 규칙이 나온다는 것을 알 수 있다.
     dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
        
for _ in range(T) :    # 차례대로 점화식에 대입하여 출력
    n = int(input())
    print(dp[n])

Point

• DP를 활용한 알고리즘
• 점화식을 먼저 찾는게 중요. 귀납법으로 할 수 있다면 먼저 차례대로 넣어보면서 찾는게 좋다