[백준 풀이_Java] 5585 거스름돈

 

 

처음 생각

 

처음에는 정말 직관적으로 큰 잔돈부터 작은 잔돈까지 차례대로 나눠서 몫(동전의 개수)을 count 에 넣고

나머지(잔액)를 change에 남겼고 change가 0 이상일 때까지 진행했다

 

 

 

 

내가 푼 방법

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int pay = Integer.parseInt(br.readLine());
		
		int change = 1000-pay;
		int count =0;
		
		while(change >0) {
			count += change/500;
			change = change%500;
			
			count += change/100;
			change = change%100;
			
			count += change/50;
			change = change%50;
			
			count += change/10;
			change = change%10;
			
			count += change/5;
			change = change%5;
			
			count += change/1;
			change = change%1;
		}
		
		System.out.println(count);
	}
}

 

 

---

 

다른 풀이

 

알아봤는데 이 문제는 그리디로 풀어야 정석인 것 같다 (사실 동전 문제가 가장 기본적인 그리디 문제인데 나만 몰랐던 것..)

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int pay = Integer.parseInt(br.readLine());
		
		int change = 1000-pay; // 잔돈
		int count =0; // 동전수
		
		int[] coins = {500, 100, 50, 10, 5, 1};
		for(int i=0; i<6; i++) {
			while(change/coins[i] > 0) {
				count += change/coins[i];
				change %= coins[i];
			}
		}
		
		System.out.println(count);
	}
}