[백준] [Python] 9095번_1,2,3 더하기_동적 프로그래밍

문제 

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

9095번: 1, 2, 3 더하기

 

풀이

#백준 9095번 문제 - 1,2,3 더하기
d = [0]*11
d[1] = 1
d[2] = 2
d[3] = 4

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

n = int(input())
for _ in range(n):
    m = int(input())
    print(d[m])

 

이번 문제는 동적 프로그래밍을 사용하였다. 

BFS로 모든 경우의 수를 찾는 방법도 있지만 쉽게 점화식을 구할수 있어서 동적 프로그래밍 알고리즘을 사용하게 되었다.

먼저

d[1] = 1

d[2] = 2

d[3] = 4

d[4] = 7

d[5] = 13

.

.

.

라는 규칙을 찾게 되어서 d[i] = d[i-1] + d[i-2] + d[i-3] (i>3) 이라는 점화식을 쉽게 구할수 있었다.

이를 코드로 구현하는데에는 어려움이 없으므로 빠르게 문제를 해결하였다.