[C++ / 11047] 동전 0

문제

11047번: 동전 0

---

문제 설명

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

 

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

---

풀이 방식

해당 문제는 주어진 값을 이용하여 어떠한 값을 최소 횟수로 만들어 내는 것이 관건이다.

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

답: 6

위 예제를 보면 4200을 최소 횟수로 만들어 내기 위해서는 1000이 4번, 100이 2번 사용되면 된다.

 

이때 1000이상의 수는 4200원 보다 큼으로 사용되지 않을 것이고

100이하의 수는 더이상 필요가 없음으로 사용되지 않을 것이다.

 

즉, 오름차순으로 주어지는 값들을 내림차순으로 4200과 대조하여서 나눈다.

몫은 따로 저장해두고 나머지는 계속 값을 대조하여 0이 될때까지 진행한다.

---

솔루션

#include <iostream>
#include <vector>

using namespace std;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  int ans = 0;
  cin >> n >> k;

  vector<int> v(n);

  for (int i = 0; i < n; i++)
    cin >> v[i];

  for (int i = n - 1; i >= 0; i--)
  {
    if (k == 0)
      break;

    if (k >= v[i])
    {
      ans += k / v[i];
      k %= v[i];
    }
  }

  cout << ans;
}