ABC144 C - Walk on Multiplication Table에서 배운

음, 곱셈표를 모른다. . 구그하면. 아무래도 이하의 이미지인것 같다.



문제문에 일단 곱셈표의 정의가 적혀 있다. 과연. .

N에 대한 접근 방식에서 가장 작은 것들을 대답하라. . 적인.

과연, 자꾸 쓰면 다녔다.

WalkonMultiplicationTable.py

N = int(input())

lis = []
from math import *
for n in range(1,floor(isqrt(N))+1):# 10^12 まで試す必要ない 10^6 で充分
    if N%n == 0:
        lis.append([n,N//n])
#print(lis)

ans = float("inf")

for a,b in lis:
    ans = min(ans,a-1 +b-1)
print(ans)
#144ms

폭 우선 탐색을 사용할 수 있을까 흥분했지만, 거기까지 필요 없었다.

step1.N을 두 요소로 분해하고 조합을 나열합니다.
step2. 조합 중에서 최단 경로 찾기

10^12가 아니라 10^6까지 충분한 이유는 다음과 같습니다.



전혀 잊고 다시 풀어.
가로 이동, 하 이동의 차이를 최소화하면 이동 거리가 최소가 될 것이라고 생각했다.

abc144c.py

N = int(input())

lis = []
from math import floor
for i in range(1,floor(N**0.5)+1):
    if N%i == 0:
        lis.append([i,N//i,abs(i-N//i)])#[下移動、横移動、下-横] を一パックにして lis に格納

lis = sorted(lis,key=lambda t:t[2])     #lis[2] 下-横の値で sort
#print(lis)
print(lis[0][0]-1+lis[0][1]-1)          #lis[0] を呼び出して答えを導出
#133ms