[java 백준] 실버2/11047번 동전 0

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

11047번: 동전 0

import java.util.Scanner;
 
public class Main {
 
    public static int n;
 
    public static int[] arr;
    public static int[] tot;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int count = 0;
        n = sc.nextInt();
        int price = sc.nextInt();
        arr = new int[n + 1];
        tot = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }
 
        while (price >= 1) {
            int len = 0;
            for (int i = 1; i <= n; i++) {
                if (price - arr[i] >= 0) {
 
                    tot[i] = price - arr[i];
 
                    len++;
 
                }
 
            }
 
            int min = tot[1];
 
            for (int i = 1; i <= len; i++) {
                if (min >= tot[i]) {
                    min = tot[i];
                }
            }
            price = min;
 
            count++;
        }
 
        System.out.println(count);
 
    }
 
}

 

동전 문제를 다이나믹 프로그래밍에서 봤어서 동전 관련문제를 찾아봤더니 이 문제가 나왔다.

근데 웬걸 그리디였다..! 

풀이는 완전탐색으로 했다! 아직 그리디 강의를 듣지 않아서 그리디 강의를 들으면 다시 수정하러 오겠다-!