[백준]동전 0 [Java/자바]

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

코드: https://github.com/irerin07/AlgorithmStudyBaek/blob/master/src/baekjoon11047.java

 

import java.util.Scanner;

public class baekjoon11047 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        int ans = 0;
        for (int i=n-1; i>=0; i--) {
            ans += k/a[i];
            k %= a[i];
        }
        System.out.println(ans);
    }
}

 

수많은 그리디 알고리즘의 문제들 중에 가장 많이 보이고 가장 기초적인 문제라고 생각한다.

 

목표값인 K를 만드는데 필요한 동전 갯수의 최솟값을 구하는 문제.

 

가장 단순히 주어진 값 K가 0이 될때까지 가장 큰수로부터 나누어주면 된다.

 

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

다른 풀이 방법이 없나하고 인터넷을 검색하면서 위의 문장이 그리디 알고리즘을 사용해서 풀 수 있다고 알려주는 힌트라고 하던데 아직 이유를 알지 못하겠다.

 

다들 그냥 저 위의 이유때문에 그리디를 사용하여 풀 수 있다고만 적어두고 이유는 그 어디에도 적어두지 않았기 때문..

 

조금 더 읽어보고 생각해보고 수정해야겠다!