[0615] 알고리즘

11047. 동전 0

  어제와 마찬가지로 그리디 알고리즘 문제. 주어지는 동전 자체가 특수하기 때문에(주어지는 동전이 서로 배수 관계), 동전의 가치를 벡터로 받고 뒤에서부터(가장 큰 가치를 가진 동전부터) 확인하여 만들어야 하는 값보다 작은 동전을 찾아내고 차례로 나눠간다.

 

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
  std::cin.tie(NULL);
  std::ios_base::sync_with_stdio(false);

  int n, k, min, num;  

  std::cin >> n >> k;

  std::vector<int> value(n, 0);
  min = 0;
  num = k;
  
  for (int i = 0; i < n; i++)
  {
    std::cin >> value[i];
  }

  for (int i = n - 1; i >= 0; i--)
  {
    if (num / value[i] != 0)
    {
      min += (num / value[i]);
      num %= value[i];
    }
  }

  std::cout << min << '\n';

  return 0;
}

  조건 때문인지 간단해서 그리디 알고리즘에 해당하는 문제라는 생각이 딱히 들지 않았다. 그냥 아무 문제 푸는 느낌...