[백준 11047] 동전 0
February 26, 2023
문제
https://www.acmicpc.net/problem/11047
아이디어
동전의 갯수를 최소로 하기 위해서는 가장 큰 동전을 우선적으로 사용해야 한다.
그렇기에 큰 동전부터 사용하고, 잔액보다 큰 동전을 만난다면 그 다음으로 큰 동전을 사용하는 과정을 반복하면 된다.
참고로 i번째 동전은 반드시 i-1번째 동전의 배수이기 때문에 이러한 그리디 알고리즘이 가능한 것이다.
만약 1000원, 600원, 100원의 동전을 가지고 1200원을 만들어야 한다고 가정했을 때에는 그리디 알고리즘이 불가능하다.
소스코드
// 입력 처리
const INPUT_NAME = "i2.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const [n, k] = input[0].split(' ').map(e => Number(e));
const coins = input.slice(1, n + 1).map(e => Number(e)).sort((a, b) => b - a);
// 문제
function solution() {
let remained = k;
let count = 0;
let i = 0;
while (remained > 0) {
if (remained >= coins[i]) {
remained -= coins[i];
count++;
} else {
i++;
}
}
console.log(count);
}
// 실행
solution();