[이코테 with Java] 거스름돈 문제 (그리디 알고리즘)

2024. 1. 18. 11:29알고리즘

1. 내가 푼 방식 

// 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다.
// 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 
// 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int coin = scanner.nextInt();
        int[] coinArray = {500, 100, 50, 10};
        int sum = 0;

        for(int i=0; i<coinArray.length; i++){
            if( i > 0 ){
                sum += coin % coinArray[i-1] / coinArray[i];
            }
            else if( i == 0 || i == coinArray.length - 1 ){
                sum += coin / coinArray[i];

            }
        }

        System.out.print(sum);
    }
}

 

2. 동빈님이 푼 방식

// 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다.
// 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 
// 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 

import java.util.*;

public class Main{
    public static void main(String[] args){
        int n = 1260;
        int cnt = 0;
        int[] coinTypes = {500, 100, 50, 10};

        for (int i = 0; i < 4 ; i++){
            int coin = coinTypes[i]; // coin이라는 변수에 동전 단위를 넣음
            cnt += n / coin; // 해당 동전 단위의 갯수를 더해줌(몫)
            n %= coin; // 해당 동전 단위로 나눈 나머지를 n에 넣어줌
            // 이렇게 하면 그 다음 인덱스에는 그 나머지를 다시 동전 단위로 나누어 몫을 구해줄 수 있음
            // 예를 들어, 500원으로 나누면 2인데, 그 나머지인 260원을 다시 100원으로 나눠줘야 함 
        }

        System.out.println(cnt);
    }
}

 

나는 처음 입력을 받을 때나, 마지막 입력을 받을 때는 나머지를 구할 필요가 없으므로, 

그 외의 경우에만 몫과 나머지 모두를 구하게 했다.

 

동빈님은 몫을 구한 다음, 나머지를 구한 값을 n에 넣어주고, 그 다음에는 자동으로 그 나머지 값에 대한 몫을 구하도록 했다. 예를 들어, 1260원을 500원으로 나누면 2이고, 그 나머지인 260을 100원으로 나눠줘야 하기 때문이다. 

 

나는 조건문을 한 번 더 거쳐야 하지만, 동빈님 코드에서는 거칠 필요 없이 바로 연산을 수행하여 효율적이다.