[SWEA|파이썬] 16800. 구구단 걷기 (D3)

문제

https://tinyurl.com/22e4lrzs

SW Expert Academy

 

 

🐍파이썬

❌ MemoryError 실패 코드

from collections import deque
T = int(input())
for test_case in range(1, T + 1):
    dx = [0, 1]
    dy = [1, 0]
    n = int(input())
    flag = 0
    grid = [[0]*(n+1) for _ in range(n+1)]
    queue = deque()
    queue.append((1, 1))
    while queue:
        x, y = queue.popleft()
        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= n+1 or ny >= n+1 or nx < 0 or ny < 0:
                continue
            if grid[nx][ny] != 0:
                continue
            grid[nx][ny] = grid[x][y] + 1
            queue.append((nx, ny))
            if nx * ny == n:
                flag = 1
                print(grid[nx][ny])
                break
        if flag == 1:
            break

최소이동거리라는 말만 보고 BFS로 풀었더니 테스트케이스 #3 10000000019 에서 메모리 오류가 발생했다.

import math
T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    arr = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:	#곱해서 n이 되는 두 수 찾기
            arr.append((i, n//i))
    for i, (x, y) in enumerate(arr):	#index, (x, y)
        arr[i] = (x-1)+(y-1)	#배열의 각 인덱스에 (1, 1)->(x, y)까지 이동거리 저장
    print("#{} {}".format(test_case, min(arr)))	#최소값(최소거리) 출력

1️⃣ 곱해서 n이 되는 두 수를 찾아 배열에 넣는다.

2️⃣ (1,1)과 가장 가까운 위치의 두 수(x, y)를 찾아 이동거리를 출력한다.