[BOJ] 11047번 : 동전 0

백준 11047번 : 동전 0

🔗 문제 링크

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

11047번: 동전 0

 

---

💬 문제

 그리디(greedy) 알고리즘 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.

 

1. 동전의 종류는 N개이며, 각 동전의 개수는 많이 존재한다.
   
   
2. N종류의 동전을 사용하여 K 금액을 만들려고 한다.
   
   - 이때 필요한 동전 개수의 최솟값을 구해주면 된다
   
   

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 N과 K가 공백을 기준으로 주어지고, 2번째 줄부터 N개의 줄에 오름차순으로 동전의 가격이 나열되어 있다. 각각을 스페이스 기준으로 잘라주고 정수화한 다음 할당해주면 된다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] JS로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

💻 풀이

이 문제는 총 2가지 방식으로 풀어볼 수 있다.

🔑 풀이1 : for문 활용

• K는 동전 금액으로 구성되어 있기에 큰 금액부터 나눠 최소 개수를 구해준다.
  
  - arr에는 동전 금액이 오름차순으로 정렬되어 있으므로 배열의 끝의 가장 큰 금액부터 시작해준다.
  
  - K를 나눴을 때의 몫이 동전의 개수가 되고, 나머지는 잔돈이기에 나머지를 K에 재할당해준다.
  
  
• 이런 방식으로 가장 큰 금액부터 가장 작은 금액까지 K를 나눠 동전의 개수 cnt를 누적해 출력해준다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s/).map(Number);
const [N, K, ...arr] = input;

console.log(solution(N, K, arr));

// 동전 개수 최솟값
function solution(N, K, arr) {
    let cnt = 0;
    for (let i=N-1; i >= 0; i--) {
        cnt += parseInt(K / arr[i]);  // 동전의 개수
        K %= arr[i];        // 잔돈
    }
    return cnt;
}

 

시간은 다음과 같이 걸렸다.

 

 

---

🔑 풀이2 : reduce 메서드 활용

• reduce를 활용하기 위해 동전 배열을 reverse()를 사용해 내림차순으로 바꿔준다.
  
  
• 처음 누적 개수는 0이고, K를 동전 금액으로 나눠 동전 개수를 cnt에 누적해준다.
  
  - reduce 메서드는 동전 배열 arr에서 동전을 하나식(cur) 꺼내준다
  
  - K를 나눴을 때의 몫이 동전의 개수가 되고, 나머지는 잔돈이기에 나머지를 K에 재할당해준다
  
  
• 이런 방식으로 가장 큰 금액부터 가장 작은 금액까지 K를 나눠 동전의 개수 cnt를 누적해 출력해준다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s/).map(Number);
let [N, K, ...arr] = input;
arr = arr.reverse();

console.log(solution(K, arr));

// 동전 개수 최솟값
function solution(K, arr) {
    return arr.reduce((acc, cur) => {
        let cnt = acc + Math.floor(K / cur);  // 동전의 개수
        K %= cur;    // 잔돈
        return cnt;
    }, 0)
}

 

 

주의할 점은 reduce 메서드 내에만 return을 해주면 reduce 메서드 내에서 cnt가 누적이 되었지만, 해당 누적값 cnt를 함수에서 반환하고 있지 않아서 undefined가 출력된다. 꼭 최종 반환값을 return 해주고 있는지 확인하자!

// 동전 개수 최솟값
function solution(K, arr) {
    arr.reduce((acc, cur) => {
        let cnt = acc + Math.floor(K / cur);  // 동전의 개수
        K %= cur;    // 잔돈
        return cnt;
    }, 0)
}

 

시간은 다음과 같이 걸렸다.