🚩 문제 링크
💻사용언어 : python,js
🤔그리디 알고리즘

🌱 문제풀이

이 문제는 그리디 알고리즘의 기본으로 이전에 이코테에서 풀었던 문제와 유사하다. 다른점은 거스름돈을 입력한다는것이다.

'현재에 가장 좋은 것 = k를 작게 만들기'

동전 개수의 최솟값을 구하기 위해서는 값이 큰 거스름돈부터 탐색해야하기에 reversed()를 이용했다.

👉 python

n, k = map(int, input().split())
coinList = list()
count = 0

for i in range(n):
    coinList.append(int(input()))

for coin in list(reversed(coinList)):
    count += k // coin #금액을 거스름돈으로 나눈 몫( 사용된 거스름돈 개수)
    k = k % coin #금액을 거스름돈으로 나눈 나머지

print(count)

👉 js

const fs = require('fs');
let input = fs.readFileSync('Q11047/input.txt').toString().split('\n');
const coin_number = input[0].split(' ')[0] // 가지고 있는 동전은 총 종류
let cost = input[0].split(' ')[1] // 만들어야하는 동전의 총 합(금액)
console.log(coin_number);
console.log(cost);

let coinList = input.slice(1,);
coinList = coinList.map((el)=> parseInt(el));
coinList.reverse(); // 큰 수부터 역순으로 
console.log(coinList);


let count = 0;
for(let i = 0; i <= coinList.length; i++){
    if (coinList[i] <= cost) {
        count += parseInt(cost / coinList[i]) // 금액을 거스름돈으로 나눈 몫(사용된 거스름돈 개수)
        cost = cost % coinList[i]; // 금액을 거스름돈으로 나눈 나머지
    }
}
console.log(count)