[JAVA] 백준 - 동전0 - 11047 (그리디)

www.acmicpc.net/problem/11047

11047번: 동전 0

 

# 풀이

스택을 이용하여 가장 단위가 큰 동전 부터 사용하면된다.

 

동전의 단위는 서로 배수 관계이므로 큰 동전 부터 사용해도 된다.

 

만약 동전끼리 배수 관계가 아니라면 적용되지 않는다.

 

예를 들어)

 

( 1, 3, 5, 6 ) 가 있다고 해보자. 8 원을 만들기 위해  큰 동전 부터 사용한다면 6원 1개 1원2개로 총 3가지 동전을 사용한다.

하지만 정답은 3원과 5원만으로 8원을 만들 수 있다.

 

# 자바 코드

import java.util.LinkedList;
import java.util.*;

class Main{
    static int n,goal;
    static int answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Stack<Integer> stk = new Stack<>();
        n = sc.nextInt();
        goal = sc.nextInt();

        for(int i=0;i<n;i++){
            stk.add(sc.nextInt());
        }

        while(!stk.empty()){
            int top = stk.pop();
            if(top > goal) continue;
            else{
                int temp = (goal/top);
                answer += temp;
                goal -= (temp*top);
            }
        }
        System.out.println(answer);

    }
}