거스름 돈 문제

[hsskey]

동전0

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

문제

📝 제약조건

• 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
• 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

💡 예시

• Input: 10 4200 1 5 10 50 100 500 1000 5000 10000 50000

  • Output: 6

• Input: 10 4790 1 5 10 50 100 500 1000 5000 10000 50000

  • Output: 12

문제 해결 과정

Step 1: 문제 이해하기

• 제약조건, input, output을 확인하여 문제를 정확히 파악합니다.

Step 2: 접근 방법

• 가장 큰 화폐 단위부터 거슬러주는 것이다.

  • 가치가 더 큰 동전은 작은 동전들의 합으로 항상 표현될 수 있기 때문

• 따라서 다음의 4단계를 거쳐서 정답을 도출할 수 있다.

  1. 500원으로 거슬러 줄 수 있는 만큼 거슬러 준다
  2. 100원으로 거슬러 줄 수 있는 만큼 거슬러 준다
  3. 50원으로 거슬러 줄 수 있는 만큼 거슬러 준다
  4. 10원으로 거슬러 줄 수 있는 만큼 거슬러 준다

• 단순히 큰 화폐 단위부터 선택하여 최적의 해를 찾을수 있는 이유는?

• 그 이유는 각 화폐 단위가 배수 관계에 속하기 때문이다. [예시] 120원을 거슬러 주어야 할때, 80원 60원 10원의 동전이 있다면? (반례)

• 최적의 해: 60 * 2 = 120원으로 2개의 동전이 필요하다

• 80원부터 거슬러준다면 총 5개의 동전이 필요할 것이다.

Step 3: 코드 설계

function 거스름돈계산(코인배열, 총액):
    총동전개수 = 0

    각 동전 in 코인배열에 대해:
        동전개수 = 총액 / 동전
        총동전개수 = 총동전개수 + 동전개수
        총액 = 총액 % 동전

    콘솔에 출력: "총액원을 거슬러 주는데 필요한 동전의 최소 개수: 총동전개수"

Step 4: 코드 구현

 const fs = require('fs')
 const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`
 const input = fs.readFileSync(filePath).toString().split('\n')

 const [n, k] = input[0].split(' ').map(Number)
 const arr = []

 let cnt = 0
 let money = k

 for(let i = 1; i <= n; i++) {
    const item = Number(input[i])
    if(item <= k) {
        arr.push(item)
    }
 }

for(let i = arr.length - 1; i >= 0; i--) {
    cnt += parseInt(money / arr[i])
    money %= arr[i]
}

 console.log(cnt)

[hsskey]

다른 풀이(유사함)

push를 그대로 다해도 몫과 나머지처리시 k값보다 큰값은 영향을 안줌

 const fs = require('fs')
 const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`
 const input = fs.readFileSync(filePath).toString().split('\n')

 let n = Number(input[0].split(' ')[0]); // 동전의 개수
 let k = Number(input[0].split(' ')[1]); // 만들어야 할 금액

 let arr = [];
 // 전체 동전(화폐 단위) 데이터 입력
 for (let i = 1; i <= n; i++) arr.push(Number(input[i]));

 let cnt = 0;
 // 가치가 큰 동전부터 확인
 for (let i = n - 1; i >= 0; i--) {
     cnt += parseInt(k / arr[i]); // 해당 동전을 몇 개 사용해야 하는지
     k %= arr[i]; // 해당 동전으로 모두 거슬러 준 뒤 남은 금액
 }

 console.log(cnt);