解説

11 つのスイッチを nn 回押すと、n(n+1)2\frac{n(n+1)}{2} 枚のコインが得られます。

このように、整数 nn を使って n(n+1)2\frac{n(n+1)}{2} として表される数は三角数と言われています。

そしてこの問題は、「NN を 最小何個の三角数の和で表されるか?」と言い換えることができます。

実は、「全ての自然数は高々 33 個の三角数の和で表される」という定理があります。
(証明は難しいので省略します。wikipedia に証明の概要が載っています。)

そのため、NN 枚のコインを獲得するためにスイッチが 11 つで良いか、スイッチが 22 つで良いかを判定することでこの問題が解けます。

スイッチが 11 つで良いかどうかは、 NN が三角数であるかどうかを確かめることで判定できます。

スイッチが 22 つで良いかどうかは、 NN 以下の三角数を列挙した後、各三角数 xx について、「NxN-x が三角数かどうか」を確かめればよいです。

NN 以下の三角数は O(N)O( \sqrt N ) 個なので、二分探索を使えば O(NlogN)O(\sqrt N \log N ) でこの問題を解くことが出来ます。