No Limitation
[DP] 1, 2, 3 더하기 4 - 백준 본문
https://www.acmicpc.net/problem/15989
15989번: 1, 2, 3 더하기 4
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2
www.acmicpc.net
동전 1과 유사한 유형으로 생각하면 된다
[DP] 동전 1 - 백준
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같..
yscho.tistory.com
이 두 문제는 DP의 대표적인 유형으로 N으로 표현 문제와 더불어 꼭 익혀놓자!
코드를 잘 익혀놓고
N = int(input())
num_list = [ int(input()) for _ in range(N)]
for num in num_list :
sum_dict = {}
for i in range(1,num+1) :
sum_dict[i] = 1
for j in [2,3] :
for k in range(j, num+1) :
if k == j :
sum_dict[k] += 1
else :
sum_dict[k] += sum_dict[k-j]
print(sum_dict[num])
'프로그래밍' 카테고리의 다른 글
| [Greedy] 멀티탭 스케줄링 - 백준 (0) | 2022.02.11 |
|---|---|
| [DP] BOJ 거리 - 백준 (0) | 2022.02.04 |
| [DP] 퇴사2 - 백준 (0) | 2022.02.04 |
| [구현] 삼각 달팽이 - 프로그래머스 (0) | 2022.02.04 |
| [Greedy] 동전0 - 백준 (0) | 2022.02.03 |
'프로그래밍' Related Articles
more
