[정올] 동전 자판기(下)

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&code=1183&sca=3050 

JUNGOL

우선 문제부터 간단하게 요약하면, 

 

철수가 가지고 있는 동전 중 최대 개수의 동전을 이용하여 자판기의 물건을 구입하는 방법을 출력해야 합니다. 

 

<Solution>

얼핏 보면 그리디 같지만, 최대 개수의 동전을 써야하므로 그리디를 바로 적용하기가 어렵습니다.

 

조금 고민을 해보면, greedy알고리즘을 적용할 수 있습니다.

 

전체 동전의 총 금액 - 만들어야 하는 금액을 최소 동전의 갯수로 만들게 되면, 남은 동전의 수가 자판기 물건을 구입하는 최대 동전의 수입니다.

 

13
4 5 2 6 3 4

문제의 예시로 이야기를 해보면, 

총 금액은 2679원이고, 13원을 만들어야 하므로, 2679 - 13 을 최소 갯수의 동전으로 만들어 보면, 남은 동전의 수가 정답이 될 것을 알 수 있습니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int W;//사용할 금액
int A[6];//각 동전 개수(갖고 있는)
int sol[6];//답

int values[6] = {500, 100, 50, 10 ,5, 1};
 
int ans;
 
void InputData(){
    cin >> W;
    for (int i=0; i<6; i++){
        cin >> A[i];
    }
}
void OutputData(){
    cout << ans << "\n";
    for (int i=0; i<6; i++){
        cout << A[i] << " ";
    }
    cout << "\n";
}

void solution(){
    // find total sum && total coins 
    int total_sum = 0;
    int total_coin = 0;
    for(int i = 0 ;i <6; i++){
        total_sum += A[i]*values[i];
        total_coin += A[i];
    }

    int to_make = total_sum - W;

    // greedy로 만들어보자
    int cur_value = 0;
    for(int i = 0; i<6; i++){
        // 몇개까지 사용가능
        int can_use = min(A[i], (to_make - cur_value) / values[i]);

        cur_value += values[i] * can_use;
        total_coin -= can_use;
        A[i] -= can_use;
        if(cur_value == to_make)break;

    }
    ans = total_coin;

}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    InputData();

    solution();
 
    OutputData();
    return 0;
}

 

<추가>

DFS등과 같은 알고리즘으로 구현하면 코드는 다음과 같고, 시간초과가 발생하게 됩니다.

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int W;//사용할 금액
int A[6];//각 동전 개수(갖고 있는)
int sol[6];//답
int tmpsol[6]; // 임시답 기록
int values[6] = {500, 100, 50, 10 ,5, 1};
 
int ans;
 
 
void InputData(){
    cin >> W;
    for (int i=0; i<6; i++){
        cin >> A[i];
    }
}
void OutputData(){
    cout << ans << "\n";
    for (int i=0; i<6; i++){
        cout << sol[i] << " ";
    }
    cout << "\n";
}
 
void dfs(int step, int num_to_make, int cnt_coins, int total_available_coins){
     
    if(step >=6){
        if(num_to_make > 0) return;
 
        // num_to_make 가 0이면
        if(ans<cnt_coins){
            copy(tmpsol, tmpsol+6, sol);
            ans = cnt_coins;
        }
        return;
    }
 
    // 가지치기
    if(total_available_coins + cnt_coins <= ans) return;
 
    // how many possible
    int cur_value = values[step];
 
    int possible = num_to_make / cur_value;
 
    possible = min(possible, A[step]);
 
    for(int i = 0; i<= possible; i++){
        tmpsol[step] = i;
        dfs(step+1, num_to_make - (cur_value*i), cnt_coins+i, total_available_coins-A[step]);
        tmpsol[step] = 0;
 
    }
    return;
 
}
 
void solution(){
    int total_available_coins = 0;
    for(int i = 0; i<6; i++){
        total_available_coins+= A[i];
    }
     
    dfs(0, W, 0, total_available_coins);
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    InputData();

    solution();

    OutputData();
    return 0;
}