[백준] 세탁소 사장 동혁 - 2720 자바 & 파이썬 풀이

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

2720번: 세탁소 사장 동혁

 

저번 글에서 그리디 알고리즘에 대해서 학습했습니다.

따라서, 그리디 알고리즘의 대표적인 문제인 잔돈 계산을 풀어봤습니다.😀

 

---

접근 방식 & 문제 풀이

 

미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다.
동혁이는 리암에게 실망했다.
리암은 거스름돈을 주는 것을 자꾸 실수한다.
심지어 $0.5달러를 줘야하는 경우에 거스름돈으로 $5달러를 주는것이다!
어쩔수 없이 뛰어난 코딩 실력을 발휘해 리암을 도와주는 프로그램을 작성하려고 하지만, 디아블로를 하느라 코딩할 시간이 없어서 이 문제를 읽고 있는 여러분이 대신 해주어야 한다.
거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈은 항상 $5.00 이하이고, 손님이 받는 동전의 개수를 최소로 하려고 한다. 예를 들어, $1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.

 

✔ 이 문제는 거스름돈을 최소한의 동전 개수로 거슬러주는 문제로, 

그리디 알고리즘을 이용하여 해결할 수 있습니다. 

 

그리디 알고리즘은 매 순간 최적의 선택을 하는 알고리즘으로, 

이 문제에서는 큰 단위의 동전부터 선택하면 됩니다. 

 

즉, 25센트 동전부터 사용할 수 있는 만큼 사용하고, 

이후에는 10센트 동전, 5센트 동전, 1센트 동전 순서로 사용할 수 있는 만큼 사용하면 됩니다.

 

---

소스코드

 

⦁ 파이썬

changes = [25, 10, 5, 1] #쿼터, 다임, 니켈, 페니
T = int(input())

for _ in range(T) :
    C = int(input())
    res = []

    for i in changes :
        res.append(C // i) #몫
        C = C % i	# 나머지 C에 할당
        
    print(*res)

✔ 파이썬에서는 코드가 참 간결했습니다.

 

 

⦁ 자바 (개선 전)

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[] changes = {25, 10, 5, 1};
		int T = sc.nextInt();

		for(int i=0; i<T; i++) {
			int C = sc.nextInt();
			int[] result = new int[4];
			
			for(int j=0; j < changes.length; j++) {
				result[j] = C/changes[j];
				C %= changes[j];
			}
			
			for(int res : result) {
				System.out.print(res + " ");
			}
		}
	}
}

✔ 파이썬 코드를 참고해서 자바로 작성해 봤는데, for 문도 너무 많고 비효율적이었습니다.
실행 시간이 파이썬의 3배 정도 더 걸렸습니다. 😥

 

 

⦁ 자바 (개선 후)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        for (int i = 0; i < T; i++) {
            int C = sc.nextInt();

            int quarter = C / 25;
            C %= 25;

            int dime = C / 10;
            C %= 10;

            int nickel = C / 5;
            C %= 5;

            int penny = C;

            System.out.println(quarter + " " + dime + " " + nickel + " " + penny);
        }

        sc.close();
    }
}

✔ 굳이 for문을 많이 사용하지 않아도 됐습니다. 전 버전은 문제를 만들어서 해결한 격이었네요.

 확실히 파이썬보다 자바가 더 어려운 것 같습니다..

 

---

 

 

---

참고 문헌 :