거스름돈 기초 문제

1. 거스름돈 2개를 사용하는 경우

www.acmicpc.net/problem/14916

14916번: 거스름돈

www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

위 두 문제들 처럼 거스름돈의 종류가 2개일때, 

최소 갯수로 거스름돈을 반환하는 방식은

 

1. 두 거스름돈 중 큰 값으로 n 을 나눴을때 나눠 떨어지면, 이 나눗셈의 몫을 카운팅하고 프로그램을 종료한다

2. 큰 거스름돈 값으로 n 이 나눠 떨어지지 않는 경우는, 작은 거스름돈으로 n 을 빼주고 하나씩 카운팅을 늘린다.

3. n 이 0 일때는 제대로 거스름돈을 준 것이므로, 카운팅한 값을 리턴하고, n 이 음수일때는 제대로 거스름돈을 주지 못한 것이므로, -1 을 리턴한다

 

- BOJ 14916 

/*
    BOJ 14916 거스름돈
    https://www.acmicpc.net/problem/14916
*/
 
#include <bits/stdc++.h>
 
#define endl "\n"
 
using namespace std;
 
int n, cnt;
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> n;
 
    while (n != 0) {
        if (n % 5 == 0) {
            cnt += (n / 5);
            break;
        } else {
            cnt += 1;
            n -= 2;
        }
    }
 
    if (n >= 0)
        cout << cnt;
    else
        cout << "-1";
 
    return 0;
}

 

 

 

2. 거스름돈의 갯수가 2개를 초과할때

www.acmicpc.net/problem/5585

5585번: 거스름돈

 

위 문제처럼 거스름돈이 2개 보다 많을 경우

거스름돈 배열을 내림차순으로 생성해서, 거스름돈 배열을 순회함과 동시에,

n - 거스름돈[i] < 0 일 때 까지 반복문 수행하면서 카운팅한다.

 

- BOJ 5585

/*
    BOJ 5585 거스름돈
    https://www.acmicpc.net/problem/5585
*/
 
#include <bits/stdc++.h>
 
#define endl "\n"
 
using namespace std;
 
int n, cnt;
int coins[6] = {500, 100, 50, 10, 5, 1};
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> n;
    n = 1000 - n;
 
    for (int i = 0; i < 6; ++i) {
        while (n - coins[i] >= 0) {
            n -= coins[i];
            cnt++;
            if (n == 0) {
                break;
            }
        }
    }
    cout << cnt;
 
    return 0;
}