[Algorithm] 욕심쟁이 알고리즘 동전 거슴름돈 문제풀이 [C++]

[개념과 원리]

동전 거스름돈(coin change) 문제는 가게에서 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하여 거스름돈을 돌려주는 방법을 찾는 문제로, 동전 문제 또는 거스름돈 문제라고 한다.

사용 가능한 동전은 500원, 100원, 50원, 10원의 네 종류가 있다고 가정하자. 욕심쟁이 방법으로 동전 거스름돈 문제를 해결하는 가장 간단하고 효율적인 방법은 거스름돈의 액수를 초과하지 않는 조건하에서 단순히 액면가가 큰 동전부터 '욕심을 부려서' 최대한 사용해서 거스름돈을 만드는 것이다.

 

[코드]

#include <iostream>
using namespace std;
 
int main() {
 
    int T; // 고객에게 돌려줄 거스름돈
    cout << "돌려줘야하는 거스름돈 = ";
    cin >> T;
    int n; // 동전의 종류 갯수
    cout << "동전의 종류 갯수 : ";
    cin >> n;
    int* COIN = new int[n]; // 동전의 액면가를 감소순으로 저장하고 있는 배열
    int* X = new int[n]; // 거스름돈으로 돌려줄 i번째 동전의 개수
 
 
    for (int i = 0; i < n; ++i) cin >> COIN[i];
 
    for (int i = 0; i < n; ++i) {
        X[i] = T / COIN[i];
        T = T - COIN[i] * X[i];
        cout << X[i] << " ";
    }
 
    delete[] COIN;
    return 0;
}

 

 

 

 

 

 

 

베타존 : 네이버쇼핑 스마트스토어