余りを出力する(AtCoder(競プロ)1日1問【12日目】【Python】)

AtCoder Beginner Contest 099 C問題

abc099.contest.atcoder.jp

競技プログラミングで使える関数を実際の問題を通して紹介いたします。

今回は「%」です。

余りを出力する 

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)

何度かでていますが、「%」。この例でいいますと、

「tを9で割った余り」が「t%9」で表されています。

以下、この問題でこのコード自体の解説を行います。

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

とするとから始まる。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)

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

つまり２５を９用と６用に分けて、ccに総計算回数を入れていくといきます。

独学プログラマー Python言語の基本から仕事のやり方まで