【競プロ精進ログ】ABC160-B

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC160-B「Golden Coins」です。

ポイント

貪欲法の練習問題です。今回は，500円硬貨を利用した方が5円硬貨よりも大きい嬉しさを得ることができるため，なるべくたくさんの500円硬貨を利用したいという気持ちになります。ですので，まずは500円硬貨を何枚使えるか調べて，残りを5円硬貨で支払うという方針でいけばOKでしょう。

通常であれば，貪欲法はforループやwhile文を利用しますが，今回は割り算の商を利用すれば簡単にそれぞれの硬貨の枚数を計算することができます。

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int main(){
  int X;
  cin >> X;

  // 500で割り切れない分
  int x;
  x = X % 500;

  int ans=0;
  // 500円で買える分だけ買う
  ans += 1000 * (X/500);
  // あとは5円で支払う
  ans += 5 * (x/5);
  cout << ans << endl;
}