[BOJ] 백준 5585 거스름돈

출처: https://www.acmicpc.net/problem/5585

 Input 
380 

 Output 

4

500원을 거슬러 받을 때, 100원 짜리 5개가 아닌 500원 짜리 1개를 돌려받습니다.

즉, 거스름돈 동전개수가 최소가 되어야 합니다.

▶ 큰 동전단위부터 최대한 거슬러주면서 잔돈이 0원이 되게합니다.

 

---

#include <iostream>
using namespace std;
int coin[] = {500, 100, 50, 10, 5, 1};
int change, coinCnt;
 
int findMaxCnt(int idx){
    int cnt = 0;
    while(true){
        if(change < coin[idx] * cnt){
            cnt--;
            break;
        }
        cnt++;
    }
    return cnt;
}
 
int main() {
    int money; cin >> money;
    // 500엔, 100엔, 50엔, 10엔, 5엔, 1엔
    
    int answer = 0;
 
    change = 1000 - money;
    for(int i=0; i < 6; i++){
        if(change == 0) break;
        // 각 동전의 최대 개수
        coinCnt = findMaxCnt(i);
 
        change -= coin[i] * coinCnt;
        answer += coinCnt;
    }
    
    // 정답 출력
    printf("%d", answer);
}