BaekJoon_11047(동전)

문제

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

11047번: 동전 0

문제풀이

매 순간 최적의 방법을 찾아내는 탐욕 알고리즘의 문제이다.

최소의 동전으로 가치의 값을 충족시켜야 하기 때문에 가치를 가장 큰 동전으로 많이 채워야 동전을 적게 쓸 수 있다.

오름차순으로 입력받는 동전을 내림차순으로 정렬하여 앞에서 부터 가치가 동전으로 나누어지는 값이면 몫은 사용된 동전 갯수로,

나머지값은 앞으로 채워야 하는 가치에 재할당 한다.

동전을 나눴으면 더 할 필요가 없기 때문에 for문에서 break문을 선언하여 성능을 향상 시킨다.

 

처음에는 if문 조건을 if(K > data)로 하여 가치가 동전보다 크면 나누는 조건을 적용하였는데 백준에 나와있는 예제는 통과하지만 제출은 오답이었다. 반례를 찾아보니 다음과 같은 경우가 있을 수 있어, 몫을 나눌 수 있을 때 조건문을 타도록 if(parseInt(K/data)) 로 변경하였다.

 

반례

3 9 1 3 5

2 4  2 3

 

코드

const answer = ([n,...arr]) => {

    let K = n.split(' ').map(Number)[1];

    // 내림차순 정렬
    const coins = arr.filter(data => data.trim()).map(Number).sort((a,b) => b-a);

    let result = 0;

    while(K > 0){
        for(data of coins){
            if(parseInt(K / data)){
                result += parseInt(K / data);
                K = K % data;
                break; 
            }
        }
    }
    console.log(result);
}

const input = [];
require("readline")
    .createInterface(process.stdin, process.stdout)
    .on("line", (line) => {
        input.push(line);
    })
    .on("close", () => {
        answer(input);
        process.exit();
    });

소스코드는 깃헙에서도 확인 가능합니다. 🤗

https://github.com/duduchi/Algorithm/tree/main/Greedy

GitHub - duduchi/Algorithm: 알고리즘 이론 및 구현 소스 정리 프로젝트 입니다.