[백준] #9095번 Dynamic Programming python
2022. 11. 28. 23:31
https://www.acmicpc.net/problem/9095
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
'''
'Programming > Algorithm' 카테고리의 다른 글
[백준] #11722번 Dynamic Programming python (0) | 2022.11.29 |
---|---|
[백준] #15988번 Dynamic Programming python (0) | 2022.11.28 |
[백준] #11053번 Dynamic Programming python (0) | 2022.11.28 |
[백준] #1149번 Dynamic Programming python (0) | 2022.11.28 |
[백준] #1912번 Dynamic Programming python (0) | 2022.11.28 |