【ABC144 C】「Walk on Multiplication Table」を解く【Python3】

abc144c

コンテスト一覧へ

 

整数Nが書かれている掛け算のマスにたどり着くまでの最小値を求める問題です。

提出
import math

n = int(input())
num_i = 0

for i in range(1, int(math.sqrt(n))+1):
    if n % i == 0:
        num_i = i

num_j = n // num_i
ans = (num_i - 1) + (num_j - 1)

print(ans)

整数i,jの小さい方は、√n以下の数字となるため、iのみをfor文を使って調べます。

nをiで割った余りが0の場合、「num_i」に代入します。

割り切れる数字のうち、移動の必要回数が少なくなるのは、より√nに近いものです(n=10000の場合、「i=10, j=1000」より「i=100, j=100」の方が移動回数が少ない)。

なので、for文を最後まで処理して、num_iに入っている数字が最小値で到達できるマス(i,j)の片方の数字です。

もう片方は「n//num_i」で出せます。

両者から最初のマス(1,1)を引き、足し合わせたものが移動回数になります。

【ABC144】解説記事

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。