<BEAKJOON / node.js> 11047 동전 0

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

// test.txt
10 4790
1
5
10
50
100
500
1000
5000
10000
50000

---

그리디 문제에 처음 도전 해보았다. 그래서 내장함수 보다는 while 이나 for 문을 사용해 케이스를 탐색해보는 식으로 해결했다.

so1 으로 제출해 문제는 맞췄지만, 시간이 1900ms나 나와버려서.. 다른 해결 방법을 찾아봤다.

 

sol1

let [n,...input] = require('fs').readFileSync('test.txt').toString().trim().split('\n');
let [num,price] = n.split(' ');
price = Number(price);

function solution(num,price,input) {
  let len = num-1;
  let answer = 0;
  while(price !== 0) {
    if(price < input[len]) len--;
    else {
      answer++;
      price -=input[len];
    }
  }
  return answer;
}

console.log(solution(num,price,input));	//12

price로 주어진 금액보다 높은 금액을 if문에서 거르고, 낮은 금액을 한 번씩 빼는 식으로 해결했다.

 

sol2

let [n,...input] = require('fs').readFileSync('test.txt').toString().trim().split('\n');
let [num,price] = n.split(' ').map(Number);

solution(num,price,input);

function solution(num,price,input) {
  let answer = 0;
  for(let i=num;i>=0;i--) {
    while(input[i]<=price) {
      price-= input[i];
      answer++;
    }
  }
  console.log(answer);
}
//12

 

if문으로 동전의 배열을 도는 대신 for문으로 뒤에서 앞으로 순회한다. 해결방식은 역으로 price 보다 작은 동전들이 while 문에 걸리면 price가 동전 값보다 작아질 때까지 카운트하고 탈출한다. 

 

---

똑같이 while 문으로 순회하기 때문에 순회방식의 차이 보다는 범위의 차이로 시간 차이가 많이 나는 것 같다. 시간복잡도나 코드의 효율성에 대해서 더 공부한 후 다시 해결해봐야겠다.