[백준/C++] 11047번 : 동전 0

문제

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

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

풀이

그리디 알고리즘을 사용하는 문제

01. vector에 오름차순으로 입력된 숫자를 넣는다

02. algorithm 헤더의 reverse 함수를 이용해 내림차순으로 정렬한다

그리디 알고리즘은 제일 큰 수부터 나누기 때문

03. 내림차순으로 정렬된 vector를 이용하여 동전 개수의 최솟값을 구한다

#include <iostream>
#include <vector>
#include <algorithm> // reverse
using namespace std;

int main(){
  int N, K, num, cnt=0;
  cin >> N >> K;
  vector<int> v;

  // 01. vector에 넣기
  for (int i=0; i<N; i++){
    cin >> num;
    v.push_back(num);
  }

  // 02. 내림차순으로 뒤집기
  reverse(v.begin(), v.end());

  // 03. 최소 개수 구하기
  for (int i=0; i<N; i++){
    if (K >= v[i]){
      cnt += K/v[i];
      K %= v[i];
    }
  }

  cout << cnt;
}