[백준 알고리즘] Node.js 11047. 동전 0

1. 문제

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

11047번: 동전 0

 

2. 풀이

- 주어진 동전의 가치에 대한 내용을 내림차순으로 정렬한다.

- k 값 보다 큰 동전이라면 넘어가고, k 값보다 작은 동전이라면 반복하여 sum 변수에 더한다

sum이 k보다 커진다면 다음 동전으로 넘어가는 과정을 반복하여 해당 k 값과 같아질 때까지 반복한다.

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [n,k] = inputs.shift().split(' ').map(Number);
const coins = inputs.map(Number).sort((a,b) => b-a);

let sum = 0;
let count = 0;

for(let i = 0; i < coins.length; i++){
  sum += coins[i];
  if(sum > k) sum -= coins[i];
  else if(sum < k) {
    i--;
    count++;
  }

  if(sum === k) break;
}

console.log(count + 1)

- 마지막에 count + 1 을 한 이유는 sum 과 k 값이 같아졌을 때, 동전을 추가하지 않는 코드를 작성했기 때문이다.

 

 

3. 정리

- 처음엔 else if 가 아닌 if 문으로 작성하여 무한 루프에 빠졌었다.

- 다른 분의 풀이를 보니 나누기와 나머지를 이용하여 푸신 분도 있었다.

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

let [N, K]= input.shift().split(' ').map(n => parseInt(n))

let cnt = 0

let q

for(let i = N - 1; i >= 0; i--) {
    let value = parseInt(input[i])
    q = Math.floor(K/value)

    if(q === 0) continue

    cnt += q
    K %= value

    if(K === 0) break
}

console.log(cnt)

- k / value :  k 보다 큰 가치의 동전인지 확인하는 코드,

- 가치가 작은 동전이라면 cnt를 증가시키고, k 를 동전의 가치로 나누고 난 나머지의 값으로 변경.

- 이후 k 가 0이 되면 종료.