Pythonで解くAtCoder(ABC173:A)

こんにちは、クルトンです！

この記事では

AtCoderのABC173(AtCoder Beginner Contest 173)のA問題をPythonを使って解説します。

 

問題のリンクを載せておきます。

atcoder.jp

この問題を解くのに必要な知識

• input関数, print関数
  
• while文
  
• 算術演算子

簡単な解法

いきなり答えは思いつかないので、具体的な値で考えてみましょう。

N = 2500のときについて考えます。

 

払った千円札の枚数をk枚とすると

 

　　k = 0    0 < 2500
　　k = 1 1000 < 2500
　　k = 2 2000 < 2500
　　k = 3 3000 > 2500

 

となるので

k = 3　であり

 

答えは

ans = k × 1000 - N
    = 3 × 1000 - 2500
    = 500

となります。

 

このように、kをwhile文で一つずつ増やしていき、「k×1000がN以上」になった時点でwhile文を終了させ、k×1000-Nを求めればよいことになります。

 

以下にサンプルコードを載せておきます

サンプルコード

atcoder.jp

少し難しい解法

今回はNが小さかったので上記の解法で解けましたが、Nが大きければ間に合いません。

なので他の解法を考えてみましょう。

 

いろいろNを変えて考えてみると、Nの下3桁だけが答えに関係することが分かります。

これは、Nの4桁目以降は1000の倍数であり、千円札できっかり払うことができるからです。

 

なので下3桁について考えるためにNを1000で割った余りについて考えます。

 

　　r = N % 1000 (rはNを1000で割った余り)

 

この余りを千円から払うので、答えは

 

　　ans = 1000 - r

 

...としたいところですがこれでは間違いです。

 

このままだと、rが0のときに答えが1000になってしまいます。

おつりは0以上999以下なのでこれはおかしいです。

なので「rが0」すなわち「Nが1000の倍数」のときに、答えが0になればよいことになります。

 

これだけのために場合分けをするのは面倒なので、1000 - r を1000で割った余りを答えとしてしまいましょう。

 

　　ans = (1000 - r) % 1000

 

これで、rが0のときもカバーできました。

 

以下にサンプルコードを載せておきます

サンプルコード

atcoder.jp

まとめ

今回は

• while文を使って解く
• 1000で割った余りを使って解く

という問題でした。

個人的にはいつものA問題としては少し難しかったかな？と思います。

 

ではまたお会いしましょう！さようなら～