AtCoder Beginner Contest 099 : C - Strange Bank
-
問題
6 と 9 の累乗の数で N をぴったり作りたい。最小で何個必要か、という問題。
1 <= N <= 100000。
-
解法
コンテスト中、累乗の数の中から一番 N に近い数を引いていくという解法しか考えていなかったが、それが最適ではないケースがある（例えば、一番 N に近い累乗数の次に近い数では割り切れるなど）。ここで 1 <= N <= 100000 という制約を生かすと、6 と 9 の累乗数それぞれで作る数を全通り試すことができる。それぞれにどれぐらいの数を作るか割り当てればそれぞれの累乗数が何個必要かはわかるので、それらの２つを足した最小値が答えになる。
-
解答
Submission #2656482 - AtCoder Beginner Contest 099
