백준 11047 동전0 Java 풀이

문제

동전 N 개가 금액을 기준으로 오름차순으로 주어질때, K 금액을 만들 수 이있는 최소한의 동전 개수를 구한다. 동전은 중복될 수 있다.

제약사항: (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000), 동전 금액은 (1 ≤ N_i ≤ 1,000,000)

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

접근

전형적인 그리디 알고리즘 문제이다. 

핵심 아이디어는 동전이 동전의 금액 (N_i) 에 따라 오름차순으로 주어지므로 가장 큰 동전부터 K 에 몇개 들어가지는지 세는 것이다.

 

두가지 접근 방법이 있을것이다.

(1) 덧셈을 이용하여 계산한다.

(2) 나눗셈을 이용하여 계산한다.

 

덧셈을 이용하는 경우 최악의 경우 (N_i = 1, k = 100,000,000) 일때 총 연산횟수 100,000,000 번으로 대략 0.5초 정도 소요된다. 문제에서 요구하는 시간제한 1초를 초과하지 않기 때문에 덧셈을 이용한 접근도 유효하겠다.
하지만 나눗셈은 O(N), 즉 O(10) 의 시간복잡도를 갖기 때문에 나눗셈을 이용한 방법이 더 나은 성능을 보장할 것이다. 

 

실제 아래의 이미지와 같이 백준에서 나눗셈이 더 나은 성능(51%, 72ms) 을 보여준다.

 

 

풀이

(1) 덧셈을 이용한 방법

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

public class Main {
    static int N, K,sum, count, i;
    static int[] coins;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        K = Integer.parseInt(input[1]);
        coins = new int[N];
        for (int i = 0; i < N; i++) {
            coins[N - i -1] = Integer.parseInt(br.readLine());
        }

        while (sum < K) {
            if (sum + coins[i] <= K) {
                sum += coins[i];
                count++;
            } else {
                i++;
            }
        }

        System.out.println(count);
    }
}

 

(2) 나눗셈을 이용한 방법

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

public class Main {
    static int N,K,count;
    static int[] coins;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        K = Integer.parseInt(input[1]);

        coins = new int[N];
        for (int i = 0; i < N; i++) {
            coins[N - i - 1] = Integer.parseInt(br.readLine());
        }

        for (int coin : coins) {
            if (coin > K) continue;
            count += K / coin;
            K %= coin; 
            if (K == 0 ) break;   
        }

        System.out.println(count);
    }
}