>6𝑖と9𝑖を分けて考えてみるとうまく解けます。6𝑖だけや9𝑖の硬貨だけのときは、使う硬貨の最小枚数を貪欲に決定できます。値段を2つに分割して、それぞれを6𝑖の硬貨で支払う場合と、9𝑖の硬貨で支払う場合として考えてみましょう。