コイン両替最小枚数

コンピュータサイエンス アルゴリズム編 / 全 2

コンピュータサイエンス アルゴリズム編 - コイン両替最小枚数

大きい順に取ると損をする組がある

コインの額面を 1 3 4 に切り替えて、金額 6 で上下の枚数が割れるところを見てください。

日本の硬貨は大きい順に取れば必ず最小になるので、貪欲でも一生気づけません。額面が自分たちで決めた値のときだけ、静かに 1 枚多い答えが出ます。

1 / 2

このスライドが付いているレッスンを開く