#그리디_알고리즘

문제

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

Solution

const input = require('fs').readFileSync('/dev/stdin')
                .toString().trim().split('\n')
const coin = input[0].split(' ')[1]
const arr = input.slice(1).reverse()

const solution = (arr, coin) => {
  let count = 0
  arr.forEach(el => {
    if(parseInt(coin / el) > 0){
      count += parseInt(coin / el)
      coin %= el
    }else if(coin % el === 0){
      return false
    }
  })
  return count 
}
console.log(solution(arr, coin))

앞서 풀었던 5585번 거스름돈과 거의 동일한 문제라고 볼 수 있다.

다른 점이 있다면
주어진 단위가 오름차순인데 내림차순이어야 최소 동전 개수를 계산하기 편하기 때문에 reverse로 정렬했고
나머지가 0이 되는 경우에는 불필요한 순회를 중단하기 위해 해당 조건을 추가했다.

참고; forEach 는 break가 없다. 대신 return false 를 쓴다