[SWEA] 16800. 구구단 걷기 (Python/D3)

---

[문제 링크] 👇

SW Expert Academy

---

풀이 방법

💡 약수 이용하기

 

N 이 10 일 경우 최소 이동 경로는 다음과 같다. 아래 그림은 곱셈표이다. 

 

2와 5는 10의 약수와 같다. 따라서 10의 약수를 구해야 하는데, 두 수의 곱의 차가 가장 작은 i와 j 를 구해야 한다.

 

(1, 1) 에서 (2, 5) 까지 가려면, i는 2가 되어야 하고, j는 5가 되어야 한다.

• i ➜ 2 - 1 = 1
• j ➜ 5 - 1 = 4 

따라서 답은 1 + 4 = 5 이다.

Solution

T = int(input())  # 테스트 케이스 수
for test_case in range(1, T + 1):
    N = int(input())

    # N 약수 구하기
    min_num = N
    x, y = 0, 0
    for i in range(1, int(N**0.5) + 1):
        if N % i == 0:
            if (N // i) - i < min_num:  # 약수의 차가 제일 작은 거
                x = i
                y = N // i

    result = (x - 1) + (y - 1)
    print(f"#{test_case} {result}")

 

 

개선할 곳

약수를 구하고 최소 차이를 찾는 부분에서 min_num 변수를 활용하지 않고, 단순히 (N // i) - i가 최소일 때 값을 바로 x와 y에 할당하도록 하여 코드를 더 간결하게 할 수 있다. 또한 min_num은 초기화를 할 필요가 없으므로 제거해도 된다.

 

개선된 코드

T = int(input())  # 테스트 케이스 수
for test_case in range(1, T + 1):
    N = int(input())
    x, y = 1, N  # 초기 값을 1과 N으로 설정

    for i in range(1, int(N**0.5) + 1):
        if N % i == 0:
            # 현재 i에 대해 (N // i) - i가 최소일 때 x, y 업데이트
            if (N // i) - i < y - x:
                x, y = i, N // i

    result = (x - 1) + (y - 1)
    print(f"#{test_case} {result}")

 

---