[백준] 11407번: 동전 0

 

 

 

---

 

문제

https://www.acmicpc.net/problem/11047

 

개념

그리디 알고리즘

 

 

실행 결과

 

 

 

구현 코드(c++)

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;        // 동전개수
  long long k;  // 최솟값

  cin >> n >> k;

  vector<long long> coins(n);

  for (int i = 0; i < n; i++) {
    // 동전의 가치 오름차순으로 주어짐
    cin >> coins[i];
  }

  int answer = 0;

  // 가장 가치가 높은 동전부터 사용
  for (int i = n - 1; i >= 0; i--) {
    if (coins[i] <= k) {
      answer += k / coins[i]; // 사용할 동전 개수 추가
      k %= coins[i]; // 다음으로 사용할 동전 찾기 위해 나누기
    }
  }

  cout << answer;

  return 0;
}

 

 

 

 

코드 설명

그리디 알고리즘을 이해하기 위한 가장 기초적인 문제이다.

탐욕 알고리즘이라고도 하는데, 매 선택 중 최선의 선택을 골라 결과를 도출하는 방식을 사용한다.

따라서 이 문제의 입출력 예시 중 1번을 참고해서 최선의 선택을 진행해보자.

 

먼저 4200원을 만들기 위한 최소한의 동전 개수는 6개이다.

4000원 = 1000원 * 4개 

200원 = 100원 * 2개

동전의 가치는 1부터 시작해서 배수로만 주어지기 때문에 나누기 연산을 사용하면 된다.

또 나누기 연산을 사용하여 나오는 몫이 곧 동전의 개수라는 것을 알아야 한다.

 

따라서 동전의 개수를 저장할 변수 answer을 선언한다.

이후 k보다 해당 동전 가치가 낮다면 해당 가치가 가질 수 있는 최대 개수를 answer에 더하고,

해당 가치로 나누어서 남은 금액을 도출한다.

 

 

 

---