[백준] 9095번 1, 2, 3 더하기 파이썬 풀이

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

9095번: 1, 2, 3 더하기

---

1. 접근 방식

• 다이나믹 프로그래밍 문제임을 알아채자.

숫자 1, 2, 3의 합으로 어떤 숫자를 나타내는 방법을 구하는 문제이다. 아래 그림으로 숫자 4를 1, 2, 3의 합으로 나타내는 방법의 개수를 구하는 방법을 알아보자.

처음에 1, 2, 3을 각각 1, 2, 3의 합으로 나타낼 수 있는 방법의 개수를 초기화해 놓는다.

4는 (3 + 1), (2 + 2), (1 + 3)으로 나타낼 수 있는데, 이때 3을 만드는 방법, 2를 만드는 방법, 1을 만드는 방법의 개수를 알고 있다면, 그냥 그 방법들에 각 1, 2, 3을 더하면 4가 만들어진다. 따라서 f(4) = f(3) + f(2) + f(1)이라는 식을 도출할 수 있고, 이를 일반화하면 f(n) = f(n - 1) + f(n - 2) + f(n - 3) (n > 3)이다.

 

 

 

2. 정답 코드

def solve(n):
    dp = [0] * 12
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

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

    return dp[n]


for _ in range(int(input())):
    print(solve(int(input())))