AOJ - Problem 0106 : Discounts of Buckwheat

• 問題文

入力された整数nに対しnグラムのそば粉を買うときの最小の金額を求める問題です。入力される範囲が[500,5000]と小さく、すべて100の倍数なので初めに計算しておくとよいです。

#include <iostream>
#include <algorithm>
using namespace std;
const int INT_MAX = 1e+7;

int main(){
	int m[5001];
	for(int i=0 ; i < 5001 ; i++ ){
		m[i] = INT_MAX;
	}
	for(int a=0 ; a < 20 ; a++ ){
		for(int b=0 ; b < 20 ; b++ ){
			for(int c=0 ; c < 20 ; c++ ){
				int cost = (a*380) - (a/5*380) + (b*550) - (b/4*330) + (c*850) - (c/3*306);
				int w = a*200 + b*300 + c*500;
				if( w <= 5000 ){
					m[w] = min( m[w] , cost );
				}
			}
		}
	}
	int n;
	while( cin >> n , n ){
		cout << m[n] << endl;
	}
}