ml_begin’s blog

Python初心者が、機械学習、画像認識、Web解析について取り組んでいきます。

AtCoder(競プロ)〜1日1問【12日目】

f:id:ml_begin:20180604073123j:plain
昨日途中でやめた分をやろうと思います。AtCoder
abc099.contest.atcoder.jp
C問題。

が、考えても結局わからなかったので他の人のやり方を見ます。

N = int(input())
res = N
for i in range(N + 1):

	cc = 0
	t = N - i
	while t > 0:
		cc += int(t % 9)
		t = int(t / 9)
	t = i
	while t > 0:
		cc += int(t % 6)
		t = int(t / 6)


print(res)

まずはじめ

	cc = 0
	t = N - i
	while t > 0:
		cc += int(t % 9)
		t = int(t / 9)

N=25とすると
t=25から始まる。
25>0なのでwhileループに入る。

cc += int(25%9)

25/9 = 2あまり7
したがって、

cc = 7
t = int(25/9) = 2

2>0なので同様に

cc += int(2%9) = 2
cc = 9
t = int(2/9) = 0

ここでt == 0となりブレイク。

次の6ループへ。

t = i
	while t > 0:
		cc += int(t % 6)
		t = int(t / 6)

t = 0なのでそもそもループに入らず終了。

	if res > cc:
		res = cc

res = 25
cc = 9なので

res = 9

これがN =25まで続くと結果が得られる。
要はこれは何がしたいのか。

	t = N - i
	while t > 0:
		cc += int(t % 9)
		t = int(t / 9)

これは上記の例では、数字を「25」を
tが(9の何乗+数値)で表せるかを調べています。
※t = 0なので6は使いません。
25 = 9*2 + 7
なので9,9,1,1,1,1,1,1,1の9回操作で引き出しが可能となります。

つまり25を9用と6用に分けて、
ccに総計算回数を入れていくということです。
これは思いつかない。
素因数分解することしか考えてませんでした。

本日は以上。