AOJ 0106 Discounts of Buckwheat

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0106

概要

そば粉をnグラム買いたいと思っている。
3つの店での1袋当たりの単価と、量、
数袋買った時の割引料金が与えられるので、
一番安くなる組み合わせの金額を出力する。

解法

5000gまでしか与えられないので全探索で十分。
ngぴったりじゃないとダメなので、ngを超える
組み合わせは含まないように注意する。

コード

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while (1) {
        int ans = 1000000;
        cin >> n;
        if (n == 0) break;
        for (int a = 0; a <= 50; a++) {
            for (int b = 0; b <= 50; b++) {
                for (int c = 0; c <= 50; c++) {
                    int sum = (380 * (5 * (a / 5))) * 0.8 + (a % 5) * 380;
                    sum += (550 * (4 * (b / 4))) * 0.85 + (b % 4) * 550;
                    sum += (850 * (3 * (c / 3))) * 0.88 + (c % 3) * 850;
                    if (a * 200 + b * 300 + c * 500 == n) {
                        ans = min(ans, sum);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}