[알고리즘][Python] 백준 9095 1, 2, 3 더하기 문제 풀이

문제 출처 : www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

---

문제 해석 : 입력된 숫자를 1, 2, 3으로만 나타낼 수 있는 경우의 수를 구하는 문제이다.

 

문제 풀이 :  DP 문제로 dp[i] = dp[i-3]+dp[i-2]+dp[i-1] 이라는 점화식을 통해서 문제를 풀 수 있다. 이와 같은 점화식이 답이 되는 이유는 다음과 같다.

1일때 -> 1

2일때 -> 1+1,  2

3일때 -> 1+1+1,  1+2,  2+1,  3

 

4일때는 1+3,  2+2,  3+1 이라는 경우를 생각할 수 있다. 

---

풀이 코드

T = int(input())
for test_case in range(T):
    N = int(input())
    dp = [0] * (11)

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

    print(dp[N])

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.