[SW Expert Academy] 16800. 구구단 걷기 | 구현 | 파이썬, 소스코드, 정답

https://swexpertacademy.com/main/main.do

SW Expert Academy

---

문제 요약

• 무한한 크기의 행렬이 있다. 행렬의 (i, j)번째에는 i*j가 적혀있다.
• N이 주어질 때 (1, 1)에서 n이 적힌 칸으로 가기 위한 최소 이동 횟수를 구하라.
• (i, j)칸에서 (i+1, j) 혹은 (i, j+1)칸으로 이동할 때의 이동횟수는 1번이다.

---

문제 조건

• 2 <= N <= 10^12

---

시행착오

• n의 범위가 엄청 커서 좀 쫄았다
• O(n)으로 풀면 시간초과일듯?

---

핵심 아이디어

• x*y = n일 때 x+y가 최소값이 되려면 x*x=n이거나 x, y가 √n 과 가까워야 한다.
• i를 int(√n)부터 1까지 순회시키며 n%i == 0인 i를 찾는다. 

---

소스코드

T = int(input())

for test_case in range(1, T + 1):
    n = int(input())

    for i in range(int(n**0.5), 0, -1):
        if n % i == 0:
            print("#" + str(test_case), i + n // i - 2)
            break