12.1 거스름 돈 [디딤돌 자료구조와 알고리즘 with C++]

12.1 거스름 돈

물건을 팔고 가장 적은 개수로 거스름 돈을 주려면 어떻게 해야 할까요?

 

큰 단위의 돈을 주는 것이 작은 단위로 주는 것보다 유리하겠죠. 탐욕 알고리즘으로 문제를 해결한다면 큰 단위부터 거스름돈을 주게 전개합니다. 큰 단위 화폐부터 작은 단위 화폐 순으로 다음의 알고르즘을 전개합니다.

 

만약 화폐 단위보다 거슬러 줘야 할 돈이 많으면 몇 개를 줄 것인지를 결정합니다. 그리고 남은 돈은 다음 단위 화폐로 넘어가서 계산합니다. 이러한 방법을 계속 수행하면 가장 적은 개수로 거스름 돈을 지불할 수 있습니다.

 

예를 들어 만원을 받고 1723원의 상품을 구입한다고 가정합시다. 거슬러 주어야 할 돈은 8277원입니다.

 

5000원<8277원이고 5000원X2>8277원이므로 5000원 화폐가 1개 필요합니다.

 

나머지는 3277원입니다. 1000원X3<3277원이고 1000원X4>3277원이므로 1000원 화폐 3개가 필요합니다.

 

나머지는 277원입니다. 277원<500원 이므로 500원 화폐는 필요 없습니다.

 

277원>100원X2이고 277원<100원X3이므로 100원 화폐는 2개 필요합니다.

 

나머지는 77원입니다. 77원>50원이고 77원<50원X2이므로 50원 화폐는 1개 필요합니다.

 

나머지는 27원입니다. 27원>10원X2이고 27원<10원X3이므로 10원 화폐는 2개 필요합니다.

 

나머지는 7원입니다. 7원>5원이고 7원<5원X2이므로 5원 화폐는 1개 필요합니다.

 

나머지는 2원이고 1원 화폐 2개 필요합니다.

 

따라서 거스름 돈 8277원을 지불할 때 최소 개수로 돌려주기 위해서는 5000원 1개, 1000원 3개, 100원 2개, 50원 1개, 10원 2개, 5원 1개, 1원 2개가 필요합니다.

 

그런데 화폐 단위가 5000원, 4000원, 1000원, 400원, 80원, 50원, 40원, 1원처럼 다를 때는 이 방법이 최선이 아닐 수 있습니다.

 

8277원에서 5000원 1개를 빼면 3277원이 남고 다시 1000원 3개를 빼면 277원이 남습니다. 80원 3개를 빼면 37원이 남고 1원 37개 필요합니다. 따라서 5000원 1개, 1000원 3개, 80원 3개, 1원 37개를 사용하여 총 44개의 거스름 돈을 돌려주어야 합니다.

 

그런데 4000원 2개, 50원 5개, 1원 27개로 돌려주면 34개의 거스름 돈을 돌려줄 수 있어 위 방법은 탐욕적인 방법이 아닙니다. 다행히 우리 나라의 화폐단위는 계산하기 쉽게 거스름 돈을 탐욕적인 방법으로 돌려주었을 때 최선입니다.

 

이제 이를 코드로 표현해 봅시다.

Program.cpp

 

먼저 화폐 단위를 열거형으로 정의하세요.

enum MType

{

    One=1, Five=5, Ten=10, Fifty=50,Hun=100,FHun=500,

    Thous=1000,FTh=5000, TenTh=10000,FTenTh=50000

};

거스름 돈을 계산할 클래스를 Calculator 이름으로 정의하기로 해요.

class Calculator

{

화폐 단위가 큰 순으로 기억할 정정 멤버 배열을 선언하세요.

    static const MType mtypes[10];

받은 화폐와 상품 가격, 거슬러 줘야 할 돈, 거슬러 줄 화폐 단위 개수를 기억할 멤버를 선언하세요.

    MType money;

    int value;

    int remain;

    int marr[10];

public:

생성자에서는 받은 화폐 단위와 상품 가격을 입력 인자로 받습니다.

    Calculator(MType money, int value)

    {

화폐 단위와 상품 가격을 입력 받은 값으로 설정하세요.

        this->money = money;

        this->value = value;

거슬러 주어야 할 돈은 받은 화폐 단위에서 상품 가격을 뺀 값이죠.

        remain = money - value;

    }

거스름 돈을 계산하는 메서드를 구현합시다.

    void Calulate()

    {

        cout<<"가격:"<<value<<", 받은 돈:"<<money<<", 거슬러 줄 돈:"<<remain<<endl;

        for(int i=0; i<10; i++)

        {

높은 화폐 단위부터 몇 개가 필요한지 계산합니다.

            marr[i] =CountChange(mtypes[i]);

만약 거슬러 주어야 할 개수가 있으면 출력하세요.

            if(marr[i])

            {

                cout<<mtypes[i]<<"원 권:"<<marr[i]<<"개, 남은 돈:"<<remain<<endl;

            }

        }       

    }

private:

특정 화폐 단위가 몇 개 필요한지 계산하는 메서드를 구현하세요.

    int CountChange(MType howmuch)

    {

        int cnt = 0;

남은 돈이 화폐 단위보다 크거나 같으면 반복합니다.

        while(remain>=howmuch)

        {

남은 돈에서 화폐 단위를 빼고 거슬러 주어야 할 개수를 1 증가하세요.

            remain -= howmuch;

            cnt++;

        }

거슬러 주어야 할 개수를 반환합니다.

        return cnt;

    }

};

const MType Calculator::mtypes[10]={FTenTh,TenTh,FTh,Thous,FHun,Hun,Fifty,Ten,Five,One};

 

int main()

{

10000원 권을 지불하여 1723원짜리 물건을 구입하였을 때로 계산할게요.

    Calculator calculator(TenTh,1723);

    calculator.Calulate();

    return 0;

}

 

▷ 실행 결과

가격:1723, 받은 돈:10000, 거슬러 줄 돈:8277

5000원 권:1개, 남은 돈:3277

1000원 권:3개, 남은 돈:277

100원 권:2개, 남은 돈:77

50원 권:1개, 남은 돈:27

10원 권:2개, 남은 돈:7

5원 권:1개, 남은 돈:2

1원 권:2개, 남은 돈:0