[SWEA/D3] 16800 : 구구단 걷기 python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYaf9W8afyMDFAQ9

SW Expert Academy

 

i가 2부터 시작하고

num이 40일 때 나올 수 있는 i,j의 순서쌍은

(2, 20), (4, 10), (5, 8), (8, 5), (10, 4), (20, 2)이다.

 

이중에서 최단거리에 있는 것은 i+j가 최소인 순간인 (5,8) 또는 (8,5)일 때이다.

그런데 생각해보면 (5, 8)일 때 이후로는 구할 필요가 없다.

순서쌍의 앞뒤값의 순서가 달라지기만 할 뿐이기 때문이다.

 

따라서 i가 num의 제곱근과 같거나 작을 때까지만

i,j의 합이 가장 작은 걸 찾는 식으로 문제를 해결하면 되겠다는 생각이 들었다.

 

이렇게 하니 num이 소수라서 그 i로도 나눠지지 않을 때가 제대로 처리되지 않는 문제가 발생했다.

그래서 flag를 만들어서 소수일 때와 아닐 때를 따로 처리했다.

 

import math
T = int(input())
for test_case in range(1, T + 1):
    num = int(input())
    # i+j의 최소값을 저장할 변수
    res = num
    # 소수인지 판단하는 플래그
    flag = 0
    
    # 2부터 num의 제곱근까지 i를 증가시킴
    for i in range(2, int(math.sqrt(num))+1):
    	# i가 num의 약수라면 i+j를 계산하고 최소값과 비교 후 업데이트
        if num%i==0:
        	res = min(i+(num//i),res)
            flag = 1
            
    # 소수라면 num-1번 이동해야 함
    if flag==0:
        res = num-1
    # 소수라면 (i-1)+(j-1)번 이동해야 함
    else:
        res = res-2
    print('#%d'%test_case,res)

그런데 이건 너무 주먹구구식의 코드인 것 같아서 코드를 개선해보았다.

 

 

import math
T = int(input())
for test_case in range(1, T + 1):
    num = int(input())
    
    # i, j 순서쌍을 저장할 리스트
    arr = []
    
    # math.sqrt(num)을 int로 형변환해주는 걸 잊으면 안됨
    for i in range(1,int(math.sqrt(num))+1):
    	# i로 나눠떨어지면 (i, j)를 리스트에 저장
        if num%i==0:
            arr.append((i,num//i))
    # 이동거리를 계산해 저장
    for i,(x,y) in enumerate(arr):
        arr[i] = (x-1)+(y-1)
    # 이동거리가 최소인 것을 출력
    print('#%d'%test_case,min(arr))