No.634 硬貨の枚数1

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 120
作問者 : しらっ亭しらっ亭 / テスター : はむこはむこ
5 ProblemId : 1705 / 出題時の順位表
問題文最終更新日: 2018-01-21 13:45:20

問題文

YUKI国の通貨の単位は円と呼ばれ、額面が三角数であるような硬貨が流通しています。
すなわち、任意の正整数 $k$ に対して、$k \times (k+1) \div 2$ 円の硬貨が流通しています。
流通している硬貨を額面を小さい方からいくつか列挙すると、$1, 3, 6, 10, 15, 21, 28, \dots $ 円です。

雪男くんは、全ての額面の硬貨を $10^{100}$ 枚持っており、$N$ 円の品物を購入しようと思っています。
その際、YUKI国の硬貨でちょうど $N$ 円となるように支払いを行います。

雪男くんは、支払いに使用する硬貨の枚数を最小化したいです。
支払いに使用する硬貨の枚数の最小値を求めてください。

入力

N

$1 \le N \le 10^{7}$
$N$ は整数

出力

答えを1行で出力してください。最後に改行してください。

サンプル

サンプル1
入力
8
出力
3

例えば、$8$ 円を支払うのに、$6$ 円の硬貨を $1$ 枚、$1$ 円の硬貨を $2$ 枚使用します。使用する硬貨の枚数は $3$ 枚となり、これが最小です。

サンプル2
入力
10
出力
1

額面 $10$ 円の硬貨 $1$ 枚の支払いが最小です。

サンプル3
入力
15415
出力
2

額面 $15$ 円と $15400$ 円の硬貨を $1$ 枚ずつの、計2枚で支払うことが可能です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。