백준-11047번/동전 0 (java)

 

문제 이해

 

N개 종류의 동전이 존재(각 종류별로 동전의 갯수는 충분히 존재함)

이 동전들로 K원을 만들 수 있는 최소 동전의 갯수를 구하면 된다.

 

문제 해결

 

동전을 입력 받을때 오름 차순으로 입력받으므로 배열의 뒷부분(가장큰 금액의 동전)부터 연산에 포함해주면 최소한의 동전으로 K원을 맞출 수 있다.

import java.util.Scanner;

public class Problem11047 {
    static int N;
    static int K;
    static int[] arr;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count=0;
        N=scanner.nextInt();
        K=scanner.nextInt();
        arr = new int[N];

        for(int i=0; i<N; i++){
            arr[i]=scanner.nextInt();
        }
        for(int i=N-1; i>=0; i--){
            if(arr[i]<=K){
                count+=K/arr[i];
                K=K%arr[i];
            }
        }
        System.out.println(count);
    }
    }

 

가장 큰 금액의 동전부터 차근차근 내려 오다가 K원보다 작으면서 가장 큰 금액의 동전을 선택하여 K원과 나눈 몫을 count에 더해준다. 이 연산을 반복하면서 최소 동전의 갯수를 구할 수 있다.