[백준] 5585 거스름돈(그리디 알고리즘)

문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

풀이

Greedy Algorithm

그리디 알고리즘은 탐욕 알고리즘이라고도 불리운다.
미래 선택은 고려하지 않고 지금 당장 최고의 선택을 하는 방식이라 탐욕 알고리즘인거 같은데 몇가지 조건(?)이 있다.

• 현재 선택이 미래 선택에 영향을 미치면 안된다.
• 하나의 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제들에 대한 최적의 해가 더해진 것이 곧 전체 문제의 최적해가 되는 경우 사용할 수 있다.

• 하나의 큰문제 : 서울에서 대전을 거쳐 부산 가야해, 가장 짧은 거리(최적의 해) = 90 + 55
• 작은 문제 1 : 서울에서 대전까지 가장 짧은 거리는 90km(최적의 해)
• 작은 문제 2 : 대전에서 부산까지 가장 짧은 거리는 55km(최적의 해)

그리디 알고리즘으로 풀지 못하는 경우

현재 선택이 미래 선택에 영향을 미치는 경우 그리디 알고리즘은 적용할 수 없다.

가장 큰 숫자를 찾는 과정에서 처음에 눈에 보이는 9를 선택했는데 3 이후 더 큰 숫자가 있었네요!

제출한 정답

const fs = require('fs');
const price = Number(fs.readFileSync('/dev/stdin').toString().trim());

const unit = [500, 100, 50, 10, 5, 1];
let remain = 1000 - price;
let result = 0;

for (let i = 0; i < unit.length; i++) {
  if (price == 0) break;

  const count = parseInt(remain / unit[i]);
  result += count;
  remain -= (unit[i] * count);
}
console.log(result);