読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


SRM 331 Div1 Medium Shopping

SRM 貪欲
問題

コインが複数種類あり、それらの金額が与えられる。各金額のコインは無尽蔵にあるとする。1~Xまでのすべての金額を支払えるようにコインを選ぶとき、このコインの枚数を最小化せよ。

やりかた

公式解説を参考にしました。
ある時点で選んだコインの総額がSで、かつ1~Sまでをすべて表現できるようなとき、次にS+1より大きい金額のコインを選んでしまうと、S+1が表現できなくなる。なのでS+1以下で最大のコインを選ぶことによって、それまでの数字をきちんと表現できつつ、少ないコインの枚数でなるべく大きな金額まで表現できる。この工程を総和がX以上になるまで繰り返す。

ソースは略。

しょげないでよBaby 眠れば治る