언어 자료구조 알고리즘/[C++]디딤돌 자료구조와 알고리즘

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

언제나휴일 2016. 4. 14. 08:18
반응형

12.1 거스름 돈

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

나머지는 7원입니다. 7>5원이고 7<5X2이므로 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

반응형