[Python] 백준 / silver / 9095 : 1, 2, 3 더하기

문제 링크 : https://www.acmicpc.net/problem/9095

평범한 배낭문제 https://www.acmicpc.net/problem/12865 랑 동전 문제 https://www.acmicpc.net/problem/9084 를 풀고 나서, 내가 dp 적 사고가 약하다고 느끼게 됐다.

그래서 1월엔 dp 랑 백트래킹 2개만 파야겠다고 생각했다. dp 는 올바른 점화식을 세우는게 너무 중요하다. 근데 이 문제를 풀고나서, 점화식 뿐만 아니라 dp table 초기 설정도 너무 중요하다는걸 느꼈다.

• dp 문제 풀 때 중요한 3가지

1. dp 의 의미 설정
2. 점화식
3. dp table 초기 설정

그리고 이 문제는 1+1+2 랑 1+2+1 를 다른 경우로 처리하는데, 그래서 난이도가 좀 더 쉬운 것 같다. 이 둘을 같은 경우로 처리했으면 동전 문제랑 비슷해질꺼라고 생각이 든다.

파이썬 코드

import sys
T = int(sys.stdin.readline())


def program():
    n = int(sys.stdin.readline())
    dp = [0]*(n+1)
    dp[0] = 1

    for i in range(n+1):
        if i >= 1:
            dp[i] += dp[i - 1]
        if i >= 2:
            dp[i] += dp[i - 2]
        if i >= 3:
            dp[i] += dp[i - 3]
    print(dp[-1])


for _ in range(T):
    program()