그리디 알고리즘

이 문제는 그리디 알고리즘 문제다.
사실 이 문제는 1년전?인가 파이썬으로 백준 한창 풀때
풀었던 문제인데 한달 뒤에 자바를 써야하는 상황이 와서
자바로 백준 문제 풀만한거 없으려나 하다가
이 문제가 난이도도 쉽고 괜찮을거같아서 다시 풀게되었다.
그니까 내가 하고싶은말은 내 티스토리 블로그에 이미 풀이가 있다는거

문제

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

풀이

그리디 알고리즘이기때문에 가장 비싼 동전부터 시작한다.

4 450
10
100
300
500

이런식으로 입력이 되었다고하면

450보다 작은 동전들만 스택에 집어넣고 [10,100,300]

사용한 동전 갯수 +=  돈/stack.pop()
돈 -= 돈/stack.pop() * stack.pop()

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

import static java.lang.Integer.parseInt;

class Main {
    public static void main(String[] args) throws InterruptedException {
        Scanner in = new Scanner(System.in);
        String[] INPUT = in.nextLine().split(" ");
        Stack<Integer> stack = new Stack<>();# 동전주머니

        int won = parseInt(INPUT[1]); # 만들어야할 돈
        
        int count = 0; #사용한 동전 갯수
		
        for(int i = 0 ; i < parseInt(INPUT[0]); i++){
            int n = in.nextInt();
            if(n > won) continue; #만약에 동전이 만들어야할 돈보다 크면 받지않음
            stack.push(n);# 아니면 스택에 push
        }
   
        while(!stack.isEmpty()){
            int coin = stack.pop();  # 가장 큰 동전 하나 꺼내고
            int temp = won/coin; #사용한 동전 갯수

            if(coin > won) continue;
            count += temp;# 사용한 동전을 count에 추가
            won -= coin * temp;# 현재 돈 - 사용한 동전 X 동전
        }
        System.out.println(count);
        System.exit(0);
    }
}

마무리

강제적으로 자바 아니면 C++을 선택해야하는 상황이라 좀 화가났는데
오랜만에 예전에 풀어봤던 문제도 풀어보니까 그떄의 추억이 새록새록
올라온다. 이때까지만해도 알고리즘이 재밌었는데..ㅜㅜ