문제

해결과정

// 동전 0
const fs = require("fs");
let [K,...coins] = fs
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt","utf8")
    .toString()
    .trim()
    .split("\n");
    
    K = K.split(" ").map(Number)    // [4200]
    N = K.shift()    // 10
    
    let myCoin = coins.map((e) => e.replaceAll('\r', ''));
    myCoin = myCoin.map(Number) ;    /// 1,5,10,50, ...
    
    let needCoinArr = [];
    for(let i=0; i<N; i++){
        if(myCoin[i]<K){
            needCoinArr.push(myCoin[i])
        }
    }
    needCoinArr = needCoinArr.sort((a,b)=>b-a);

    let money = K[0]
    let cnt = 0;
    for(let j=0; j<N; j++){
        if(needCoinArr[j]<money){
            cnt += parseInt(money/needCoinArr[j])       /// 2.5를 그냥 2로 넣어주는것
            money = money%needCoinArr[j]
        }
    }    
    console.log(cnt)
   

문제를 보자마자 어떻게 풀어야될지 바로 생각이 들었다.

처음에는 저 종류의 동전이 하나씩만 있는건가 라고 생각했는데

자세히 읽어보니 동전의 종류일뿐 동전의 갯수는 무한대 라는 암묵적인 룰이 있는걸 확인하고

순차적으로 빼주면 되겠다는 생각이 들었다.

needCoinArr 라는 배열에 내가 구하고자 하는 돈은 4200 원 이니깐

myCoin 그것보다 작은 숫자들로만 만들어진 배열을 새롭게 만들었다.

그리고 그 배열을 sort 로 가장 큰 금액순으로 다시 바꿔준 후

money 라는 함수로 우선 목표 금액인 4200 값을 초기에 할당한 후

현재 금액인 money 와 needCoinArr[j] 를 비교해서 더 작다면 그 수로 나누고

나눴다면 그건 그 동전을 사용한거니깐 그만큼 cnt 에 숫자를 더해주었따.

그리고 다음 연산을 위해 money 를 needCoinArr[j] 로 나눈 나머지값을

다시 money 로 새롭게 할당해줌으로써

필요한 동전의 갯수를 구하는 방식이였다.

vs코드상에서는 예제 2개다 모두 통과가 되었지만

아쉽게도 이 코드는 백준에서는 제출 실패가 뜬다.

코드상에 오류가 있는것 같은데 아직은 찾지 못한 상황이다.

다른풀이

const fs = require('fs');
let [N, ...nums] = fs.readFileSync('dev/stdin').toString().trim().split(/\s+/).map(Number);

let price = nums.shift();
nums.sort((a, b) => b - a);

let count = 0;

for (let i = 0; i < nums.length; i++) {
  if (price < nums[i]) {
    continue;
  } else {
    const value = Math.floor(price / nums[i]);
    price -= value * nums[i];
    count += value;

    if (price === 0) {
      break;
    }
  }
}

console.log(count);

출처 : https://parkparkpark.tistory.com/m/92

출처 : https://webruden.tistory.com/1039

느낀점

풀고나서 래퍼런스를 찾아보니 그리디 알고리즘이라는 일종의 문제형식으로 자주 사용되는 문제였던 것 같다.

풀이방식은 내가 생각한것과 동일하지만 코드길이는 좀 더 짧게 풀 수 있는 방법들도 많았던 것 같다.