[백준/DP] 9095번: 1, 2, 3 더하기 (실버3, python)

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

9095번: 1, 2, 3 더하기

아이디어

경우의 수를 구하는 문제라서 dp로 풀기로 했다.

먼저 식을 도출하기 위해 1~5까지 구하고, 의심되는 식을 사용해서 7과 10의 경우의 수를 구해보았다.

1	1	1
2	1+1 2	2
3	1+1 2+1 1+2 3	4
4	1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1	7
5	1+1+1+1+1 1+1+1+2 -> 이 조합으로 4가지 1+1+3 -> 이 조합으로 3가지 1+2+2 -> 이 조합으로 3가지 2+3 -> 이 조합으로 2가지	13
. . .

위와 같이 n번째의 경우의 수는 n-1, n-2, n-3번째 경우의 수를 모두 더한 값 이었다.

즉, dp[idx] = dp[idx-1] + dp[idx-2] + dp[idx-3] 이다.

전체 코드

import sys 
input = sys.stdin.readline

n = int(input())
nums = [int(input()) for _ in range(n)]

maxi = (max(nums) + 1)
dp = [0] * maxi
dp[1], dp[2], dp[3] = 1, 2, 4

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

for num in nums:
    print(dp[num])