[백준] #9095번 Dynamic Programming python

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

9095번: 1, 2, 3 더하기

 

 

DP로 점화식으로 풀어내는 문제이다.

 

 

해당 문제를 풀기 위해서 손으로 써보길 바란다.

 

number가 1일 경우

1 : 1

number가 2일 경우

2 : 1 + 1

2 : 2

number가 3일 경우

3 : 1 + 1 + 1

3 : 1 + 2

3 : 2 + 1

3 : 3

number가 4일 경우

4 : 1 + 1 + 1 + 1

4 : 1 + 1 + 2

4 : 1 + 2 + 1

4 : 2 + 1 + 1

4 : 3 + 1

4 : 1 + 3

4 : 2 + 2

 

위와 같이 1, 2, 4, 7, 13, ...의 수가 나오는 것을 볼 수 있다.

 

따라서,

solution(n) = solution(n - 1) + solution(n - 2) + solution(n - 3)

의 점화식을 얻을 수 있다.

 

코드는 아래와 같다.

import sys

num = int(input())

num_list = []

def solution(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
    else :
        return solution(n-1) + solution(n-2) + solution(n-3)

for _ in range(num):
    num_list.append(solution(int(input())))

for i in num_list:
    print(i)
'''
3
4
7
10
'''