日刊競プロ ABC 182 - C - To 3 -
問題文
各桁に 0 が出現しないような正の整数 N が与えられます。
N の桁数を k とします。N の桁を 0 個以上 k 個未満消して、残った桁をそのままの順序で結合することで 3 の倍数を作りたいです。
3 の倍数を作ることができるか判定し、作ることができるなら作るのに必要な最少の消す桁数を求めてください。
制約
1≤N<10**18
N は各桁に 0 が出現しない整数
考えたこと
与えられた数からどの桁か選んでを消して、３になるかを確かめる。そのため、コンビネーションが必要だと考えた。pythonのlibraryであるitertoolsを使って実装すれば良いと考えた。
そのままの数（０桁を消した場合）で３で割り切れるかをはじめにチェックして、１桁、２桁、、、N-1桁を消していった場合で割り切れるかをチェックしていく。最後まで割り切れなかった場合は-1を出力する
import itertools
N = input()
length = len(N)
i = 0
for i in range(length):
for v in itertools.combinations(N,length-i):
temp = int("".join(v))
if temp%3==0:
print (i)
quit()
print (-1)サメちゃんかわいい