[그리디] 1183. 동전 자판기

[정올] 동전 자판기(下)

📝 풀이 과정

💡 핵심 아이디어

전체 동전의 총 금액 - 구입하려는 물건의 값(W)
이 차액을 최소한의 동전의 개수로 만들어야 한다.

남은 동전의 수가 자판기에서 사용할 수 있는 최대 동전의 수가 되는 것이다.

예를 들어, 문제에서 주어진 테스트케이스에서
동전의 총 금액이 2679원이고, 구입하려는 물건의 값이 13원이다.

2679 - 13 = 2666원이 남기 때문에
2666원을 최소한의 동전 개수로 만들고 나면, 남은 동전의 수가 우리가 구하고자 하는 정답이 된다.

👩🏻‍💻 제출 코드

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int W = Integer.parseInt(br.readLine()); // 목표 금액
		int[] coin = {500, 100, 50, 10, 5, 1}; // 동전 단위
		int[] count = new int[coin.length]; // 동전 갯수
		int balance = 0; // 남은 금액
		int answer = 0; // 총 돈전 갯수
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < 6; i++) {
			count[i] = Integer.parseInt(st.nextToken());
			answer += count[i];
			balance += count[i] * coin[i];
		}
		
		balance -= W;
		
		for(int i = 0; i < coin.length; i++) {
			if(count[i] == 0) continue;
			
			for(int j = count[i]; j >= 1; j--) {
				if(balance - coin[i] * j >= 0) {
					balance -= coin[i] * j;
					answer -= j;
					count[i] -= j;
					break;
				}
			}
		}
		
		System.out.println(answer);
		
		for(int n : count) {
			System.out.print(n + " ");
		}
		
		
	}

}