[Java] 백준 풀기 5585 - 거스름돈

자바 백준 5585번

브론즈 2

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

5585번: 거스름돈

 

 

 

 

 

문제 보기

구현: 그리디 알고리즘

 

 

 

 

 

문제 풀기

잔돈의 종류중 가장 큰 값으로 나누어 그 나머지를 임시 저장하고 그 몫인 잔돈의 개수를 합한다. 임시 저장한 나머지를 그 다음 크기의 잔돈으로 나누어 그 나머지를 임시 저장하고 그 몫인 잔돈의 개수를 누적하여 더한다.

이 과정을 제일 작은 잔돈이 나올때까지 반복하며 각 잔돈의 개수를 누적해 합한뒤 결과를 출력한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main (String args[]) {
        Scanner sc = new Scanner(System.in);
        
        int payment = sc.nextInt();  // 입력 받은 지불할 돈
        int result = changeCalculator(payment);
        
        System.out.print(result);
    }
    
    public static int changeCalculator (int payment) {
        int[] coins = {500, 100, 50, 10, 5, 1};  // 잔돈의 종류
        int[] changeCount = new int[coins.length];  // 잔돈의 개수를 저장할 배열

        int remainingChange = 1000 - payment;  // 받을 잔돈

        for (int i = 0; i < coins.length; i++) {
            changeCount[i] = remainingChange / coins[i];  // 해당 잔돈의 개수 계산
            remainingChange %= coins[i];  // 남은 잔돈 업데이트
        }

        int totalChangeCount = 0;  // 받을 잔돈에 포함된 잔돈의 총 개수
        for (int count : changeCount) {
            totalChangeCount += count;
        }
        
        return totalChangeCount;
    }
    
}