[SWEA] 16800. 구구단 걷기

16800. 구구단 걷기

문제 풀이

• 주의할 점은 그냥 num이 아닌 int(num ** 0.5) 로 두어야 한다.
  아니면 시간 초과 발생
  
• (1, 1)에서 (i, j)까지 가는 횟수 : (i - 1) + (num // i - 1)
  ex) (1, 1) 에서 (3, 5)까지 이동 거리
  x축을 1부터 3까지 이동 : 2
  y축을 1부터 5까지 이동 : 4
  총 6번 이동하였음
  
• 따라서, (i, j) - (1, 1) 결과값의 x축과 y축의 합

t = int(input())

for k in range(1, t + 1):

    num = int(input())
    arr = []

    for i in range(1, int(num ** 0.5) + 1):
        if num % i == 0:  # i: 곱해서 num이 되는 수 
            arr.append((i - 1) + (num // i) - 1)  # (i, j) = (i, num // i)

    print(min(arr))

틀린 풀이

최단 거리라고 해서 bfs로 접근했는데 3번째 입력값에서 시간 초과가 발생했다.
visited 리스트에 지나온 [x, y]들을 저장하고 있어서 공간이 많이 차지하는 것 같다.

    visited = []
    def bfs(x, y):

        queue = deque()
        queue.append([x, y, 0])

        while queue:
            a, b, cnt = queue.popleft()

            dx, dy = [1, 0], [0, 1]

            for i in range(2):
                nx = a + dx[i]
                ny = b + dy[i]

                if 0 <= nx < num and 0 <= ny < num and (nx + 1) * (ny + 1) == num:
                    # print(cnt)
                    return cnt

                if 0 <= nx < num and 0 <= ny < num and [nx, ny] not in visited:
                    visited.append([nx, ny])
                    queue.append([nx, ny, cnt + 1])


    print(f"#{k} {bfs(0, 0) + 1}")