#11047. 동전 0
문제링크
Problem
- 동전의 종류 N
- 동전을 적절히 사용해 합을 K로 만드려고 한다.
Goal: K를 만드는데 필요한 동전 개수의 최솟값 구하기
Solution
동전의 가치는 오름차순으로 주어지고
이전 가치보다 항상 몇 배 더 크다.
4200
1000 4
100 2
6개
4790
4000 4 790
500 1 290
100 2 90
50 1 40
10 * 4
12개
12
1, 3, 4, 5
5 2 2
1 2
4개
하지만
4 * 3
3개
위와 같은 상황이 일어날까?
동전의 가치가 이전 가치의 배수이기에 일어날 수 없을 것이다.
1 Try
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #include <iostream> #include <vector> using namespace std; vector<int> costs; int main() { int i, n, goal, answer = 0; cin >> n >> goal; costs.resize(n); for(i = 0; i < n; ++i) { cin >> costs[i]; } while(goal != 0) { if(goal >= costs[i-1]) { goal -= costs[i-1]; answer++; } else i--; } cout << answer << '\n'; return 0; }
|