[백준-5585번 자바/java] 거스름돈 _디버깅의 눈물

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

5585번: 거스름돈

 

 

 

 

 

거스름돈 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

32526

20795

17772

63.765%

문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

출력

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

예제 입력 1 복사

380

예제 출력 1 복사

4

예제 입력 2 복사

1

예제 출력 2 복사

15

 

 

 

 

 

---

 

 

 

 

체크 포인트

 

1. 그리디 알고리즘(Greedy Algorithm) 이용

 

-현재의 가장 최적의 답을 선택해 적합한 결과를 도출해내는 '그리디 알고리즘'을 이용하는 문제이다.

-그리디 알고리즘의 대표적 문제 유형으로는 활동 선택 문제나 거스름돈 문제 등이 있다.

 

-거스름돈 문제의 경우 동전의 종류가 서로 배수의 관계에 있다.

-1원이 동전의 종류로 존재하기 때문에 지불하지 못하는 경우는 존재하지 않는다.

-그리디 알고리즘이므로 가능한 큰 수의 동전을 사용해서 최소의 거스름돈 동전 개수를 찾아야한다.

 

 

 

 

2. 동전의 종류를 coins[] 배열에 입력

 

    	// 동전의 종류를 담는 배열 초기화
    	coins = new int[6];
    	
    	coins[0] = 500;
    	coins[1] = 100;
    	coins[2] = 50;
    	coins[3] = 10;
    	coins[4] = 5;
    	coins[5] = 1;

 

-먼저 동전의 종류를 coins[] 배열에 입력해 활용하였다.

 

 

 

 

 

3. 거스름돈 = 1000 - 지불할 금액(N)

 

    	// 1000-지불한 금액 = 거스름돈을 매개변수로 전달
    	solution(1000-N);

 

 

 

 

 

 

 

4. 큰 수의 동전부터 거스름돈 처리(그리디 알고리즘)

 

 

    	// 큰 단위의 동전부터 거스름돈 처리 
    	for(int i=0; i<6; i++){
    		// 거스름돈보다 i번째 종류의 동전이 더 작거나 같다면,
    		if(coins[i]<=changes){
    			answer += changes/coins[i];
    			changes = changes%coins[i];
    		}
    	}

 

 

-현재 사용할 수 있는 가장 큰 수(최적)의 동전을 이용해 거스름돈을 구성하는 '그리디 알고리즘'을 활용한다.

-해당 동전을 더이상 사용할 수 없는 경우, 다음으로 사용할 수 있는 가장 큰 동전을 이용해 동일한 로직을 반복하며 최적해를 구해나간다.

 

 

 

-예시1)의 경우, 거스름돈은 1000원 - 380원 = 620원이고, 거스름돈을 구성하는 최소의 동전 개수는

 

1)현재 사용할 수 있는 가장 큰 수의 동전은 500원이므로, 620원을 500원으로 나눈 몫1을 동전 개수에 추가하고, 나머지인 120원이 새로운 거스름돈이 된다.

 

2)현재 사용할 수 있는 가장 큰 수의 동전은 100원이므로, 120원을 100원으로 나눈 몫1를 동전 개수에 추가하고, 나머지인 20원이 새로운 거스름돈이 된다.

 

3)현재 사용할 수 있는 가장 큰 수의 동전은 10원이므로, 20원을 10원으로 나눈 몫2를 동전 개수에 추가하고, 나머지는 0원이므로 사용한 동전의 총 개수 4(1+1+2)를 출력한다.

 

 

 

 

 

 

풀이

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

public  class Main {
	
	static int[] coins;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());

    	// 지불한 금액
    	int N = Integer.parseInt(st.nextToken());
    	
    	// 동전의 종류를 담는 배열 초기화
    	coins = new int[6];
    	
    	coins[0] = 500;
    	coins[1] = 100;
    	coins[2] = 50;
    	coins[3] = 10;
    	coins[4] = 5;
    	coins[5] = 1;
    	
    	// 1000-지불한 금액 = 거스름돈을 매개변수로 전달
    	solution(1000-N);
    	
    }
    
    
    
    static void solution(int changes){
    	
    	// 정답을 담는 변수
    	int answer = 0;
    	
    	// 큰 단위의 동전부터 거스름돈 처리 
    	for(int i=0; i<6; i++){
    		// 거스름돈보다 i번째 종류의 동전이 더 작거나 같다면,
    		if(coins[i]<=changes){
    			answer += changes/coins[i];
    			changes = changes%coins[i];
    		}
    	}
    	
    	System.out.println(answer);
    }
    

} // end of Main