[SWEA][D3][Python] 16800. 구구단 걷기

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

SW Expert Academy

 

import math
 
T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    arr = []
    arr2 = []
 
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            arr.append(i)
            arr.append(n // i)
 
    j = 0
    while len(arr)>j:
        a = arr[j] + arr[j + 1]-2
        arr2.append(a)
        j+=2
 
    print("#{} {}".format(test_case, min(arr2)))

📌 n이 주어졌을 때 어떤 두 수를 곱해야 n이 나오는 지 그 과정을 풀어내기 힘들었다.

for i in range(1, n):
        if n % i == 0:
            arr.append(i)
            arr.append(n // i)

 시간 초과가 발생하였다.

 

▪ 루트를 사용한다. n이 주어졌을 때 두 수의 가장 큰 수는 루트n * 루트n이기 때문이다.

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

시간 초과가 발생하지 않고 해결할 수 있었다.