백준 5585번 거스름돈

문제 링크입니다: https://www.acmicpc.net/problem/5585

그리디 알고리즘을 적용하여 푸는 문제였습니다.

동전 배열을 내림차순으로 정렬하고 각 동전을 최대한 많이 사용하면 풀 수 있는 문제였습니다.

#include <iostream>

using namespace std;

 

int pay;

int coin[] = { 500, 100, 50, 10, 5, 1 };

 

int minCoin(void)

{

        int total = 1000 - pay;

        int cnt = 0;

 

        //greey하게 접근

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

                 //해당 동전을 최대한 사용한다

                 while (total - coin[i] >= 0)

                 {

                         total -= coin[i];

                         cnt++;

                         if (total == 0) //잔돈을 모두 반환했을 경우 반복문 탈출

                                 break;

                 }

        return cnt;

}

 

int main(void)

{

        cin >> pay;

 

        cout << minCoin() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~