11047번

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

11047번: 동전 0

이번 문제는 그리디 알고리즘 문제이다.

나는 처음 그리디 알고리즘이 정확히 무엇인지 모르고 이 문제를 풀었다 하지만 한번에 맞추었다.

그렇지만 그리디 알고리즘이 무엇인지는 알고 가야 할 것 같아서 정리 해보려고 한다.

 

그리디 알고리즘이란?

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

그리디 해법은 그 정당성 분석이 중요하다. - 단순히 가장 최적이라고 생각하는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 확인한다.

 

즉, 그리디 알고리즘은 자신의 생각에 최적이라고 생각하는 것부터 탐색하여 해를 구하는 것이라고 생각한다.

 

그래서 11047번은 동전의 최소갯수를 구하는 방법을 구성하는 것으로, 주어진 K값보다 작거나 같은 값들을 모은다.

그리고 그 값들 중에 K를 나누었을 때 몫이 0이아니면 갯수에 포함하고 K를 나눈 값으로 나눈 나머지로 변환하는 방식으로 로직을 짰다.

정답 코드는 아래와 같다.

package backjoon;

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

public class b11047 {
    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());
        ArrayList<Integer> coins = new ArrayList<>();
        for(int i=0; i<n; i++){
            int tmp = Integer.parseInt(br.readLine());
            if(tmp<=k){
                coins.add(tmp);
            }
        }
        int count = 0;
        for(int i=coins.size(); i>0; i--){
            if(k/coins.get(i-1)!=0){
                count+=k/coins.get(i-1);
                k=k%coins.get(i-1);
            }
        }
        System.out.println(count);
    }
}