読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

yukicoder No375 立方体のN等分 (1)

考え

同じ方向からN - 1枚の平面で切断するのが最大なので、TMaxはN - 1

下図のA方向からの平面の切断数をa、B方向はb、C方向はc、とすると
TMinはa + b + cの最小の値となる。
なので、aの値を全探索をして、残りのb、cの値を決めて最小値を求める。
N = (a + 1) * (b + 1) * (c + 1)となるように全探索を行う。
f:id:tookunn:20160605011553p:plain

ソースコード

N = int(input())
maxAns = N - 1
minAns = 10**11
yaku = []
i = 1
while i * i <= N:
	if N % i == 0:
		yaku.append(i)
	i += 1
for a in yaku:
	for b in yaku:
		if N % (a * b) == 0:
			c = N // (a * b)
			minAns = min(minAns,a - 1 + b - 1 + c - 1)
print(minAns,maxAns)