[백준] 11047번: 동전 0

11047번: 동전 0

 

전형적인 그리디 문제! 그리디의 기초! 동전 문제! 입니다.

 

문제 조건 중에서 눈여겨 봐야 할 부분은 A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수 부분입니다.

문제에서 배수라는 조건이 주어졌기 때문에 금액이 큰 동전부터 이용하는 그리디 해법이 적용될 수 있습니다.

 

 

#include <iostream>
using namespace std;

int N, K;
int coin[11];

void input() {
  cin >> N >> K;

  for (int i = 0; i < N; i++) {
    cin >> coin[i];
  }
}

int minCoinNumber() {
  int ans = 0;
  for (int i = N - 1; i >= 0; i--) {
    if (coin[i] <= K) {
      ans += K / coin[i];
      K %= coin[i];
    }
  }
  return ans;
}

void printAnswer(int ans) {
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);

  input();
  int ans = minCoinNumber();
  printAnswer(ans);

  return 0;
}