[백준 - 5585번] 거스름돈 - JAVA 정리 및 해설

안녕하세요. 오늘 풀어볼 문제는 거스름돈입니다. 이 문제는 그리디 방식의 문제입니다. 

 

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

5585번: 거스름돈

거스름돈의 경우는 구현 문제라고 해서 문제를 풀었습니다. 그래서 이문제를 일일히 if문을 통해서 문제를 풀어내보려했습니다.

while(Cost>0)을 통해서 루프를 통해서 Cost 값을 계속 줄여가면서 0원이 될때까지 줄어가는 방식으로 구현했습니다.

/** 2019. 9. 24. 오후 6:42:03
 * @author ventulus95
 */
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 cost = Integer.parseInt(br.readLine());
		cost = 1000-cost;
		int num =0;
		while(cost>0){
			if(cost/500>0){
				num += cost/500;
				cost = cost%500;
			}
			else if(cost/100>0){
				num += cost/100;
				cost = cost%100;
			}
			else if(cost/50>0){
				num += cost/50;
				cost = cost%50;
			}
			else if(cost/10>0){
				num += cost/10;
				cost = cost%10;
			}
			else if(cost/5>0){
				num += cost/5;
				cost = cost%5;
			}
			else{
				num += cost/1;
			}
		}
		System.out.println(num);
	}
}

 

 

문제는 이게 시간 초과가 나옵니다. 이게 왜 시간 초과가 걸릴까요?

 

이 알고리즘 풀이 방식은 While문을 통해서 계속 루프가 돌면서 if문을 계속 거치면서 중복적으로 계산이 너무 많아지는게 문젠데요. 

왜 그러냐면, 650원이라고 했을때 > 500원을 빼고 150원이 됬을때 다시 500원을 빼는 작업을 합니다. > 안되므로 100원을 빼는 작업을 하기때문에 중복적으로 500원이나 100원등이 계속 중복 계산이 되기때문에 시간초과가 발생합니다.

 

그럼 이걸 왜 그리디로 풀어야 할까요?

그리디는 말그대로 탐욕적으로 문제를 풀어내려가는겁니다. 얼핏보면 DP랑 비슷한 것 같은데, (뭐 따지고 보면 좀 다르긴하지만) 그리디는  필요한 것만 뽑아서 혹은 필요없어보이는건 제끼는 걸로 방식으로 진행합니다. 

 

이 문제를 통해서 그리디의 방식을 설명해보자면, 우리는 어차피 계산할때부터 애초에 금액이 1000원의 남은 잔돈을 가지고 나머지 금액을 계속 빼가는 방식입니다.  즉, 500원을 최대한 빼주면 적어도 500원이 새로 생기는 경우는 없을 겁니다.  우리는 이런 추측을 바탕으로 100원이나 50원 10원 5원에도, 적용할 수 있습니다. 

 

/** 2019. 9. 24. 오후 6:42:03
 * @author ventulus95
 */
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 cost = Integer.parseInt(br.readLine());
		int[] coinArr = {500, 100, 50, 10, 5, 1};
		cost = 1000-cost;
		int num =0;
		for(int i=0; i<6; i++){
			if(cost/coinArr[i]>0){
				num += cost/coinArr[i];
				cost = cost%coinArr[i];
			}
		}
		System.out.println(num);
	}
}

 

각 금액별로 딱 한번씩만 값을 나누면서 그 값을 num에 저장하면됩니다. 그러면 정답이 나오게 됩니다.