[백준] 5585번: 거스름돈

 

 

---

 

문제

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

 

개념

그리디 알고리즘

 

 

실행 결과

 

 

구현 코드(c++)

#include <iostream>
using namespace std;

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

  int n;
  cin >> n;               // 타로가 지불할 돈
  int change = 1000 - n;  // 잔돈

  int coins[6] = {500, 100, 50, 10, 5, 1};  // 잔돈 동전 배열
  int answer = 0;                           // 잔돈 매수

  for (int i = 0; i < 6; i++) {
    if (coins[i] <= change) {
      answer += change / coins[i];  // 사용할 동전 개수 추가
      change %= coins[i];  // 다음으로 사용할 동전 찾기 위해 나누기
    }
  }

  cout << answer;

  return 0;
}

 

 

 

 

코드 설명

아래 문제를 풀고 나서 더욱 쉽게 이해할 수 있었다.

[백준] 11407번: 동전 0

 

 

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

나누기 연산을 사용하여 나오는 몫이 해당 동전의 가치에서 사용할 수 있는 최대 동전 개수임을 깨달으면 쉽게 풀린다.

 

문제에서 구하고자 하는 것은 거슬러 주는 돈이므로 change를 1000-n으로 선언한다.

이후 해당 가치가 가질 수 있는 최대 동전 개수를 answer에 더하고 나눠주는 과정을 반복하면 끝!

 

 

---