[그리디 알고리즘] 백준 11047번 동전0 문제 Java 풀이

문제

- 준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1

10 4200

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 1 

6

예제 입력 2 

10 4790

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 2 

12

플러스 테스트케이스

1 2

1

> 이건 꼭해보세요

나의 풀이

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        //동전의 갯수, 목표 원
        Scanner sc = new Scanner(System.in);
        int coinCount = sc.nextInt();
        int money = sc.nextInt();
        int[] coin = new int[coinCount];
        
        for(int i =0; i<coinCount; i++){
            coin[i]= sc.nextInt();
        }
        //혹시모르니 코인들 오름차순 정렬
        Arrays.sort(coin);
        //money보다 커지는 coin을 캐치
        int count = 0;
        int balance = money;
        while(true){
            for(int i =coin.length-1;i>=0; i--){
                if(coin[i]<=balance) {
                    balance-=coin[i];
                    break;
                }
            }
            count++;
            if(balance==0){
                break;
            }
        }
        System.out.println(count);
        sc.close();
    }
}

>> 14번째까지는 백준에서 콘솔입력을 input으로 받기 때문에 콘솔입력을 받기 위한 세팅부분이고 실제 계산하는 알고리즘은 16번째줄부터 보시면 되겠습니다. 저는 만약 4500원이 들어온다면 5천원은 안되고 1원으로 4장 계산해야한다는 것을 캐치하였습니다. 1000과 5000사이의 존재하는 4500이라는 값은 5000일때는 걸리면 안되고 1000일때 걸려야 했습니다. 그런데 오름차순으로 동전의 값이 증가하게되면 5000이라는 시점에 coin[i]와 balance의 값에 true 값이 리턴이 될것이고 유효한 숫자인 1000이라는 숫자의 index는 이미 지났기 때문에 ArrayIndexException을 반환할지도 모를 가능성이 높습니다. 따라서 1000에 딱 coin[i]와 balance의 값에 if문이 실행되도록 최댓값부터 감소시켰습니다.(21라인 : for문을 보시면 이해하실수 있을 것입니다) 그이후부터는 간단합니다. while루프는 무한루프로 돌고 for문으로 현재 balance(잔액)에서 coin[i]값을 뺴주면 되고 0이 되는 시점에 무한루프를 탈출하고 찍으면됩니다.