SWEA D3 16800. 구구단 걷기 (python)

구구단 걷기

풀이

무한한 A*B 행렬(인덱스가 1부터 시작하는)의 칸이 있다고 할 때, 각 칸은 각 인덱스를 곱한 숫자가 들어간다.

예시에서도 말했듯이 9*9라면 구구단값이 들어있다.
이런 행렬이 있다고 가정하고, 주어지는 N의 값이 있는 칸으로 이동하려고 할 때, 가장 적은 이동을 할 수 있다면 몇 칸을 이동하는지를 출력하는 문제이다.

기본적으로 root값인 인덱스에 가까울수록 가장 적은 이동수를 제공한다.

예시는 아래와 같다.

값이 16이 있는 칸으로 움직여야할 때

(1,1) -> (1,16)	15칸(0+15) 이동
(1,1) -> (2,8)	8칸(1+7) 이동
(1,1) -> (4,4)	6칸(3+3) 이동

따라서 (4,4)로 움직이는 것이 가장 적은 이동이고, 이동 칸 수는 6칸이다

이런 생각을 가지고 아래처럼 풀었다.
N과 시작 지점을 정해주고, for문을 N의 루트값부터 1까지 돌도록해서, 찾아내는 방법을 시도해서 해결했다. 또한 시간초과 또한 나지 않았다.

# root값 즉, 정사각형에 가까울 수록 거리가 짧아짐
T = int(input())
for testcase in range(1, T+1):
    N = int(input())
    # 시작 점 a,b
    sa = 1
    sb = 1
    i = 0
    j = 0
    for n in range(int(N**(1/2)), 0, -1):
        if N % n == 0:
            i = n
            j = N // n
            break
    answer = (i-sa) + (j-sb)
    print(f'#{testcase} {answer}')