[백준] 9095번 - 1, 2, 3 더하기

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

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

문제 풀이

dp	1	2	3	4	5	6	7
n	1	2	4	7	13	24	44

• dp[1] = 1, dp[2] = 2, dp[3] = 4
• dp[4] = dp[1] + dp[2] + dp[3] = 7
• dp[5] = dp[2] + dp[3] + dp[4] = 13
• 점화식 : $f(n) = f(n-1) + f(n-2) + f(n-3), \space (n >= 3)$

import sys
input = sys.stdin.readline

t = int(input())
num = [1, 2, 3]

for _ in range(t):

    goal = int(input())
    dp = [0] * (goal + 1)
    dp[0] = 0

    for i in range(goal + 1):
        if i == 1:
            dp[i] = 1

        elif i == 2:
            dp[i] = 2

        elif i == 3:
            dp[i] = 4

        elif i > 3:
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3])

    print(dp[goal])

---

표로 점화식 열심히 찾아보려고 했는데, 잘 안보여서 고민하다가 힌트를 봤다. 사실 일정 시간 이후로 안풀리면 힌트를 보는게 맞는 방식인지는 모르겠지만 일단은 그렇게 공부중이다.

정답이 허무할 정도로 간단해서 허탈한 기분이 들었다. DP 문제가 어려워서 많이 풀려고 노력중인데 한달 후에는 잘 풀 수 있었으면 좋겠다.