K_程式人

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=102

#include <iostream>

#include <iomanip>

#include <fstream>

#include <algorithm>

#define CNUM 6

#define cinF 1000000000

#define DOL 501

using namespace std;

int main() {

    int price[CNUM] = {5, 10, 20, 50, 100, 200};

    int coin[CNUM], dpShop[DOL], dpUser[DOL];

    int ans;

    double money;

    while(1) {

        money = 0;

        for(int i = 0; i < CNUM; i++) {

            cin >> coin[i];

            money += coin[i];

        }

        if(money == 0)

            break;

        cin >> money;

        money *= 100;    

        for(int i = 0; i < DOL; i++) {

            dpShop[i] = cinF;    

            dpUser[i] = cinF;    

        }

        dpShop[0] = 0;

        dpUser[0] = 0;

        ans = cinF;

        for(int i = 0; i < CNUM; i++) {

            for(int j = 0; j < DOL; j+=5) {

                if(j - price[i] >= 0 && dpShop[j - price[i]] != cinF)

                    dpShop[j] = min(dpShop[j], dpShop[j - price[i]] + 1);

            }

        }

        for(int i = 0; i < CNUM; i++) {

            for(int j = 0; j < coin[i]; j++) {

                for(int k = DOL - 1; k >= 0; k-=5) {

                    if(k - price[i] >= 0)

                        dpUser[k] = min(dpUser[k], dpUser[k - price[i]] + 1);

                }

            }

        }

        for(int i = (int)(money + 0.5); i < DOL; i++)    // + 0.5 �� double �� int ����

            ans = min(ans, dpShop[i - (int)(money + 0.5)] + dpUser[i]);

        cout << setw(3) << ans << endl;

    }

    return 0;

}