백준 11047번 동전 0

#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;
}