백준 11047 - 동전 0 (자바 - 그리디)

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

11047번: 동전 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 의 배수)

 

* 출력

첫째 줄에 K 원을 만드는데 필요한 동전 갯수의 최솟값을 출력한다.

 

 

* 해결 과정

동전 갯수를 최소화 시켜야 하므로 가장 가치가 높은 동전을 우선적으로 많이 사용하게끔 로직을 작성했다.

가장 가치가 높은 동전으로 목표 합 K 에 최대한 가까이 도달한다.

매 반복마다 동전 가치를 합산하면서 사용한 동전 갯수를 계산한다. 만약 목표치를 초과하게 되면 마지막으로 합산한 만큼의 동전값 만큼 뺄셈을 수행한 다음, 다음번 반복부터는 그 다음으로 높은 가치를 가진 동전을 사용하게끔 인덱스 값을 바꿔준다.

위와 같은 과정을 합산한 결과가 목표 합 K 와 일치하게 될 때까지 반복해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] inputArray = br.readLine().split(" ");

        int coinCount = Integer.parseInt(inputArray[0]);
        int goalMoney = Integer.parseInt(inputArray[1]);

        int[] coinArray = new int[coinCount];
        int maxIndex = 0;
        for(int i = 0; i < coinArray.length; i++){
            int coin = Integer.parseInt(br.readLine());
            coinArray[i] = coin;

            if(coinArray[i] <= goalMoney){
                maxIndex = i;
            }
        }

        int reqCount = 0;
        int sum = 0;
        while(true){
            int money = coinArray[maxIndex];
            sum += money;
            
            if(sum < goalMoney){
                reqCount++;
            }
            else if(sum > goalMoney){ // 합산 결과 목표보다 초과될 경우 뺄셈 이후 인덱스 낮춤
                sum -= money;
                maxIndex--;
            }
            else{ // 목표금액을 맞췄을 경우
                reqCount++;
                break;
            }
        }

        bw.write(reqCount + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

사용하는 동전을 최소화 하기 위해 가치가 가장 높은 동전부터 사용하는 방식으로 로직을 최적화 했다.

목표 값 K 를 딱 맞추기 위해 할 수 있는 동전의 조합이 여러가지가 있을 수 있는 만큼 전체적으로 봤을 때는 반드시 최적해가 구해진다는 보장은 없으나, 최소 갯수를 구하기 위해 매 반복마다 뒤의 결과와는 상관없이 가치가 높은 동전을 사용해가며 목표 값에 가까워지는 식으로 로직을 작성하였으므로 그리디 알고리즘 문제에 해당된다.