동적 프로그래밍
-
[WEEK04/DAY02] 백준 9084번: 동전SW Jungle/TIL (Today I Learned) 2022. 10. 15. 01:47
https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net DP (다이나믹 프로그래밍)의 대표 문제같은 느낌이다. 문제 해석 : T번의 테스트 케이스가 주어지고, N가지 동전으로 금액 M을 만드는 모든 방법의 수를 출력해야 한다. $N(1 \leq N \leq 20)$개의 동전 종류가 주어진다. 동전은 개수 제한 없이 쓸 수 있다. 동전들의 가치 $N_i (1 \leq N_i \leq 10000)$는 오름차순으로 정렬되어 주어진다. 만들어..