https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는
www.acmicpc.net
1 -> 1개
2 -> 1+1, 2 -> 2개
3 -> 1+1+1, 1+2, 2+1, 3 -> 4개
4 -> 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2 -> 7개
5 -> 23개
...
f(n) = f(n-3) + f(n-2) + f(n-1)의 규칙성을 가진다.
test_case = int(input())
dp = [0] * 11
dp[1], dp[2], dp[3] = 1, 2, 4
for _ in range(test_case):
n = int(input())
for i in range(4, n+1, 1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
print(dp[n])
'알고리즘 > 백준 (Pyhthon)' 카테고리의 다른 글
| [알고리즘] 백준 11055 가장 큰 증가 부분 수열 / python, dp (0) | 2020.06.13 |
|---|---|
| [알고리즘] 백준 16768 Mooyo Mooyo / python, dfs, simulation (0) | 2020.06.10 |
| [알고리즘] 백준 12100 2048(Easy) / python, dfs (1) | 2020.03.16 |
| [알고리즘] 백준 14620 꽃길 / python (0) | 2020.03.14 |
| [알고리즘] 백준 16956 늑대와 양 / python (0) | 2020.03.13 |
