回答編集履歴
1
n=14の説明を少し修正
answer
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
|
-
解説見ずに私が考案した考え方を載せておきます。（例題が全て正解したのは確認済み）
|
|
1
|
+
解説見ずに私が考案した考え方を載せておきます。DPを使った解法です。（例題が全て正解したのは確認済み）
|
|
2
2
|
|
|
3
3
|
n<100000で引出金額として取りうるのは次の12通りです。
|
|
4
4
|
```
|
|
@@ -9,7 +9,7 @@
|
|
|
9
9
|
d(2) 以降は、1回目の引出金額をnの超えない範囲で引出パターンから選び、d(n-1回目金額)が最小になるものを回とします。
|
|
10
10
|
例えば、
|
|
11
11
|
n=2の場合は、1回目の引出金額が1、二回目以降はd(2-1) == d(1) しかないので、解は2。
|
|
12
|
-
n=14の場合は、1回目の引出金額が9,6,1の3パターンあるので、d(5)、d(8)、d(13)のうち最小になるものを探して+1したものが解。このうちd(8)
|
|
12
|
+
n=14の場合は、1回目の引出金額が9,6,1の3パターンあるので、d(5)、d(8)、d(13)のうち最小になるものを探して+1したものが解。このうちd(8)とd(13)が3で最小なのでd(14)は4。
|
|
13
13
|
|
|
14
14
|
このようにn=1から順に計算していき、結果を逐次記録しておけばO(n)の計算量で結果が求まります。
|
|
15
15
|
下記のコードでだいたい300msくらいの処理時間です。
|