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

Python

[Python] 백준 알고리즘 온라인 저지 9095 1, 2, 3 더하기

9095 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

문제는 1, 2, 3의 합으로 n개의 수들을 나타내는 방법의 수를 묻는 문제이다. DP와 점화식을 이용하여 풀이하는 어렵지 않은 문제였다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
    a = int(input())
    dp = [0, 1, 2, 4, 7]
    for i in range(5, a+1):
        dp.append(dp[i-3]+dp[i-2]+dp[i-1])
    print(dp[a])

---

풀이

점화식을 만들기 위해 작은 a들의 경우의 수를 생각해본다. 0 = 0, 1 = 1, 2 = 2, 3 = 4, 4 = 7로 계산되고 이 값들을 dp로 리스트에 넣어 선언해준다. 점화식은 dp(n) = dp[i-3]+dp[i-2]+dp[i-1] 으로 앞의 3 dp의 합으로 계산된다. 

이를 이용하여 for문을 작성하는데 미리 작성해놓은 dp를 이용하여 새로운 dp값들을 추가하여 a값에 도달할 때까지 계산하는 것이다. 깊게 들어가 점화식에 대해서는 블로그에 따로 정리하여 놓았으니 여기서는 설명하지 않겠다. 결과 값으로 dp에서 a번째의 수를 출력하면 풀이는 끝이다.

---

 풀이 결과