[BOJ/python] 9095: 1, 2, 3 더하기

문제

✔️ silver 3
다이나믹 프로그래밍

문제 흐름

DP는 초반에 점화식(?)을 어떻게 파악하고 잡느냐가 중요한 것 같다.
이 문제에서는 다음과 같은 패턴을 통해 파악할 수 있다.

최대한 눈에 잘 보이게 표현하려고 노력했는데 패턴이 보였을지 모르겠다.
n을 1, 2, 3의 덧셈으로 표현하고자 한다면 n을 표현할 수 있는 경우의 수는 다음과 같다.

1. n-1의 경우의 수 -> 1 + n - 1
2. n-2의 경우의 수 -> 2 + n - 2
3. n-3의 경우의 수 -> 3 + n - 3

각각 n-1, n-2, n-3 모두 같은 방법으로 1부터 시작하여 구해지기 때문에 반복적으로 구해지게 된다.

코드

# 1, 2, 3 더하기
# dp

import sys
input = sys.stdin.readline

def dp (n: int): # bottom-up
    if n == 1: # 1
        return 1
    elif n == 2: # 2 1+1
        return 2
    elif n == 3: # 3 2+1 1+2 1+1+1
        return 4
    
    lst = [0 for i in range(n + 1)]
    lst[1] = 1
    lst[2] = 2
    lst[3] = 4

    for x in range(4, n + 1):
        lst[x] = lst[x - 1] + lst[x - 2] + lst[x - 3]
    
    return lst[n]


if __name__ == "__main__":
    t = int(input())
    for tastcase in range(t):
        n = int(input())
        result = dp(n)
        print(result)

마무리

생각보다 고민을 많이 했다.
항상 이 점화식(??)을 찾는 부분이 어려운 것 같다.
좀 더 눈치와 수학적인 머리가 필요한 부분이다.