[BOJ] 11047번 - 동전 0

🔥 접근

1. 그리디 알고리즘을 사용하여 접근(현재 상황에서 가장 최적인 선택) → 가장 액수가 큰 동전부터 많이 사용하는 것
2. COINS 배열을 뒤에서부터 순회하여 K에 대해 나눠준다. (큰 값 부터 적용) 이때 나눠져서 나온 값을 count 에 더해준다.
3. 2번과정에서 나누어진다면 K 값에서 시작한 amount 를 줄여나가며 다음 순회시에 적절한 count 가 더해지도록 한다.

🚨 주의할 점 🚨

만약 동전이 배수가 아닌, 1, 9, 10 과 같이 구성되어있다면 18을 구할때
그리디 알고리즘을 사용한다면 값이 틀리게 됨!

따라서 이와같은 경우에는 다이나믹 프로그래밍(DP) 방식을 사용해야 함
(큰 문제를 작은 문제로 나누어서 해결하는 방법, 필요할 때 다시 계산하지 않고 재활용하는 방식 === memoization)

🧑‍💻 코드

const fs = require('fs');

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const input = fs.readFileSync(filePath, 'utf8').toString().trim().split('\n');

const [N, K] = input.shift().split(' ').map(Number);
const COINS = input.map(Number);

let amount = K;
let count = 0;

for (let i = N - 1; i >= 0; i--) {
  count += Math.floor(amount / COINS[i]);
  amount %= COINS[i];
}

console.log(count);

🔗 관련 링크

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