お金の支払い

https://paiza.jp/works/mondai/double_roop_problems/double_roop_problems__payment

最初全く考えつきませんでした。
たぶん、(1,X,Y)=Zの組み合わせを全部考えて
それらの中でそれぞれの数が最小になるのを選べばよいわけです。
だけど、これらをどうやって多重ループにすればいいのか？が考えつきませんでした。

ただし、
・ 2 ≦ X , Y ≦ 1000
・ X != Y
・ 1 ≦ Z ≦ 3000
うーんと。
まず1円というのがあるので、
ひとまず、テストケースを元に考えます。
500 1000 300なので、
X = 500
Y = 1000
Z = 300。
ZがXやYよりも少なければ、問答無用で１円をZ枚分使うのが最小になりますね。だから300が答えになります。

テストケース２だと
50 100 855
X = 50
Y = 100
Z = 855
XよりYが大きければそっちを限界まで使いますね。
この場合、Z//Y = 8をcntにいれて、余りをsumに入れればいいわけなので sum = Z % Y (55）
次に、sum // X = 1 をcntに加えます。　また余りを sum %= X （5)にいれます。
余った分がそのまま枚数になるので、cnt+=sumってことですね。
cnt = 14となるので間違ってはないですね。
じゃあ、このロジックで行ってみます。
多重ループじゃないけどとりあえずチャレンジで。

```py
X,Y,Z = map(int,input().split())
sum = Z
cnt = 0
if Z < Y and Z < X:
    cnt = Z
else:
    if X < Y:
        cnt = Z // Y
        sum = Z % Y
        cnt += sum // X
        sum %= X
        cnt += sum
    else:
        cnt = Z // X
        sum = Z % X
        cnt += sum // Y
        sum %= Y
        cnt += sum
        
print(cnt)

```
これでやってみるとテストケース１つだけ不合格でした。
入力はこれですね。170 999 1020
なるほど、余りが残った単位よりも小さい場合も考えないとだめですね。

```py
X,Y,Z = map(int,input().split())
sum = Z
cnt = 0
if Z < Y and Z < X:
    cnt = Z
else:
    if X < Y:
        cnt = Z // Y
        sum = Z % Y
        if sum > X:
            cnt += sum // X
            sum %= X
        cnt += sum
    else:
        cnt = Z // X
        sum = Z % X
        if sum > Y:
            cnt += sum // Y
            sum %= Y
        cnt += sum
        
print(cnt)

```

で良いと思ったんですが。
なんと、Ｘが170だと、1020を6枚で割り切れるので　こちらで計算して出した22枚よりも
こっちが少ない結果に。
となると、XかYのどっちかで割り切れた場合

```py
X,Y,Z = map(int,input().split())
sum = Z
cnt = 0
if Z < Y and Z < X:
    cnt = Z
elif Z % X == 0 or Z % Y == 0:
    if X < Y:
        cnt = Z // Y
    else:
        cnt = Z // X
else:
    if X < Y:
        cnt = Z // Y
        sum = Z % Y
        if sum > X:
            cnt += sum // X
            sum %= X
        cnt += sum
    else:
        cnt = Z // X
        sum = Z % X
        if sum > Y:
            cnt += sum // Y
            sum %= Y
        cnt += sum
        
print(cnt)

```
ぜんぜんややこしくなってきちゃいましたね。。。
時間もなかったのでギブアップして答えみました。

下のforループは、
num_xはXの枚数で、ちょうどZをXで割った商が最大限払える枚数になる
num_yはYの枚数なので、ちょうどZをYで割った商が最大限払える枚数になる

下のnum_oneは1円の枚数ですね。

```py
x, y, z = map(int, input().split())
#ansが最初z枚分となってるのは、1円のときで、そのあと他のケースと比較する時に使う

ans = z

for num_x in range(z // x + 1):
    for num_y in range(z // y + 1):
        #とりあえずｘと yの硬貨だけでz以下になる組み合わせを探す
        if num_x * x + num_y * y <= z:
            #もし上の結果がｚと同じだったらnum_oneは０となる
            num_one = z - num_x * x - num_y * y
            # ansが1枚全部を使った枚数より小さかったらこっちを採用する
            if num_x + num_y + num_one < ans:
                ans = num_x + num_y + num_one

print(ans)

```
入力が500 1000 300の場合
ans = 300
最初のfor文は、0まで
2番めのfor文は 0まで
num_xは0、num_y = 0のときにz=300以下になるので
num_one = 300 - 0 - 0 = 300
2番目のifは、300 < 300 で不成立のため300で答え

入力が50 100 855の場合
ans = 855
最初のfor文は、０〜17まで
2番めのfor文は 0〜8まで
num_xは1、num_y = 8のときにz=855以下になるので
num_one = 855 - 50 - 800 = 5
2番目のifは、1＋8＋5=13で答え

入力が10 1000 1000の場合
ans = 1000
最初のfor文は、０〜100まで
2番めのfor文は 0〜1まで
num_xは0、num_y = 1のときにz=1000以下になるので
num_one = 1000 - 0 - 1000 = 0
2番目のifは、0＋1＋0=1で答え

入力が170 999 1020の場合
ans = 1020
最初のfor文は、０〜６まで
2番めのfor文は 0〜１まで
num_xは６、num_y = 0のときにz=1020になるので
num_one = 1020 - 1020 = 0
2番目のifは、６＋０＋０=６で答え

---

理解するのが大変で、確認タイムがかなりオーバーしましたが
なんとかロジックの確認ができました。
なかなかうまくできているなァと思いました。

最初に書いたように、
(1,X,Y)=Zの組み合わせを全部考えればいいところまではわかったのですが
後で答えを見て考えて、まずそもそもXとYが固定なので、
１〜Z/X枚と１〜Z/Y枚の中でループすると考えればよかったのだと気づきました。
固定の部分と数を変えれる部分をみて、数を変えれる部分はループにできそうだ、ということに
気づけばよかったのだなと思います。

ifをつかって組み合わせを探し出すっていうパターン、今まで
多分なかった気がするので新鮮でした。
こういうやり方覚えておこう。