つのスイッチを 回押すと、 枚のコインが得られます。
このように、整数 を使って として表される数は三角数と言われています。
そしてこの問題は、「 を 最小何個の三角数の和で表されるか?」と言い換えることができます。
実は、「全ての自然数は高々 個の三角数の和で表される」という定理があります。
(証明は難しいので省略します。wikipedia に証明の概要が載っています。)
そのため、 枚のコインを獲得するためにスイッチが つで良いか、スイッチが つで良いかを判定することでこの問題が解けます。
スイッチが つで良いかどうかは、 が三角数であるかどうかを確かめることで判定できます。
スイッチが つで良いかどうかは、 以下の三角数を列挙した後、各三角数 について、「 が三角数かどうか」を確かめればよいです。
以下の三角数は 個なので、二分探索を使えば でこの問題を解くことが出来ます。