アルゴ式-お菓子 (2)
- 最短で求めるにあたって以下の様に考えてしまっていたが、３倍を有効活用するためにあえて+1をするパターンがあることに気づくまで時間がかかってしまった。
- 最初の1日は1個お菓子を作る
- そこからはNを超えない範囲で常に3倍
- ３倍するとNを超える値になったらひたすら１日１個のお菓子を作る
- そこから以下の様に考え直した
- もしNが３の倍数ならば3で割る。そうでなければ-1をする。
- これをNが0になるまで繰り返す。
これによって最短のX日目にちょうどN個になるまでを逆算で求めていけば最も効率的な経路をたどることに気づいた。
while(countOkashi > 0){
if (countOkashi % 3 == 0){
countOkashi /= 3;
} else {
countOkashi--;
}
count++;
}
この解法に至るまで時間がかかったことについて
- 「１日目から順に考える」「Nを超えるまでは３倍して最後は+1連打するのが最も最短」という考えに頭が支配されて問題がおかしいのではないかと疑うくらい凝り固まってしまった。
- 正直なんで逆算する解法をひらめいたかもよくわからないが、当問題は確認問題のため公式の模範解答や解説もなく20分ほど悩んでしまった。この程度で２０分くらい悩んでしまった挙句問題を疑いだすという自分の愚かさ、センスのなさにかなり傷ついた。先が思いやられる。