백준 11047 - 동전 0

YongHyun·2023년 5월 9일

Java 백준 코딩테스트

백준, 프로그래머스 - 코딩테스트

목록 보기

32/43

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 $A_i$ 가 오름차순으로 주어진다. (1 ≤ $A_i$ ≤ 1,000,000, $A_1$ = 1, i ≥ 2인 경우에 $A_i$ 는 $A_i$ -1의 배수)

출력

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

예제 입력 1

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1

6

문제 풀이

입력된 K 를 주어진 동전을 이용하여 모두 더한 값이 K와 같아질 수 있는 동전의 개수를 구하는 문제이다.

이런 유형의 문제는 그리디 알고리즘에 전형적으로 등장하는 것이라고 한다.

그리디 알고리즘

탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고 하는데 현재 상태에서 보는 선택지 중 최선의 선택지가 천체 선택지 중 최선의 선택지라고 가정하는 알고리즘이라고 한다.
그리디 알고리즘의 핵심 이론은 다음과 같다.

해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.

적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.

해 검사 : 현재까지 선택한 해 집합이 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

주어진 동전의 종류가 다음과 같다면 이 동전들을 배열에 넣어준다.
1
5
10
50
100
500
1000
5000
10000
50000

coins[] = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000];

그리고 배열의 끝 인덱스의 값부터 K 를 나눠주면서 몫을 결과값을 저장할 변수(count)에 더해준다. K 가 나눠질 수 있다면 나머지 값을 K로 업데이트 시켜준다.

ex) K = 4200
coins[9] = 50000 (x)
coins[8] = 10000 (x)
coins[7] = 5000 (x)
coins[6] = 1000 (4200 / 1000) = 4 -> count += 4, K = 4200 % 1000
coins[5] = 500 (x)
coins[4] = 100 (200 / 100) = 2 -> count += 2, K = 200 % 100
...

이를 코드에 적용해보면 다음과 같다.

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

public class 동전0 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] coins = new int[N];

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

        int count = 0;
        for(int i = coins.length - 1; i >=0; i--) {
            if(K / coins[i] != 0) {
                count += K / coins[i];
                K %= coins[i];
            }
        }
        System.out.println(count);
    }

}