[Algorithm] 동전 거스름돈 알고리즘

사용자 환경 : IntelliJ IDEA 2017.3.2 (Community Edition)

Build #IC-173.4127.27, built on December 26, 2017

JRE: 1.8.0_152-release-1024-b8 x86_64

JVM: OpenJDK 64-Bit Server VM by JetBrains s.r.o

Mac OS X 10.12.6

동전 거스름돈 알고리즘이란?

만약 1300원의 거스름돈을 손님에게 건네줘야 한다면 어느 조합으로 건네줘야 가장 적은 수의 동전을 건네주는가를 구하는 문제이다.

1300원의 경우, 500원짜리 2개, 100원짜리 3개로 총 5개가 가장 적은 수를 건네는 조합이다.

public class CoinChange {

    private int ten;
    private int fifty;
    private int hundred;
    private int fiveHundred;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        CoinChange cc = new CoinChange();

        System.out.print("거스름돈을 입력하세요 : ");
        int change = sc.nextInt();

        while(change >= 500) {
            change -= 500;
            cc.fiveHundred++;
        }
        while(change >= 100) {
            change -= 100;
            cc.hundred++;
        }
        while(change >= 50) {
            change -= 50;
            cc.fifty++;
        }
        while(change >= 10) {
            change -= 10;
            cc.ten++;
        }

        System.out.println("10원짜리 " + cc.ten + "개");
        System.out.println("50원짜리 " + cc.fifty + "개");
        System.out.println("100원짜리 " + cc.hundred + "개");
        System.out.println("500원짜리 " + cc.fiveHundred + "개");
        System.out.println("총 동전 개수는 " + (cc.ten + cc.fifty + cc.hundred + cc.fiveHundred) + "개 입니다.");
    }
}

(간단한 문제라서 따로 메소드를 사용하진 않았습니다.)