最初全く考えつきませんでした。
たぶん、(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となるので間違ってはないですね。
じゃあ、このロジックで行ってみます。
多重ループじゃないけどとりあえずチャレンジで。
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
なるほど、余りが残った単位よりも小さい場合も考えないとだめですね。
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のどっちかで割り切れた場合
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円の枚数ですね。
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をつかって組み合わせを探し出すっていうパターン、今まで
多分なかった気がするので新鮮でした。
こういうやり方覚えておこう。