読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.32 貯金箱の憂鬱

yukicoder 貪欲法

問題

問題概要

硬貨の枚数を最小枚数に変更する。

解法

まず、合計金額を求める。それを1000円、100円、25円、1円の順に優先的に変換していけばいい。

ミス

なし。

コード

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int main(void){
    int l, m, n;
    cin >> l >> m >> n;
    int sum = 0;
    sum += l * 100 + m * 25 + n;

    int ans = 0;
    //1000円硬貨に
    sum -= 1000 * (sum / 1000);
    //100円硬貨に
    ans += sum / 100;
    sum -= (sum / 100) * 100;
    //25円硬貨に
    ans += sum / 25;
    sum -= (sum / 25) * 25;
    //1円硬貨に
    ans += sum;
    cout << ans << endl;
    return 0;
}