[브론즈1]백준 2609번(최대공약수와 최소공배수) - 코테공부 35일차(2025.02.25)

문제유형

수학(최대 공약수, 최소 공배수)

풀이 방법 도출 과정

1. 두개의 자연수의 최대공약수와 최소공배수를 구하는 문제이다.

2. 최대공약수와 최소공배수를 곱한 것이 두개의 자연수를 곱한 것이 된다.

3. 최대공약수를 먼저 구한 후, 이를 이용해 최소공배수를 구하는 방식으로 문제를 해결할 수 있다. 

시간 복잡도

시간 복잡도는 N(M + M_list)인데 그냥 O(N)으로 표현할 수 있다. 

코드 및 간단설명

문자열의 특성을 활용하였다. 

M, N = map(int, input().split())
M_list = []
N_list = []

for i in range(1, M + 1):
    if M % i == 0:
        M_list.append(i)

# M의 약수 중 N의 약수인 것 찾기 (공약수)
for j in range(len(M_list)):  
    if N % M_list[j] == 0:
        N_list.append(M_list[j])
        
print(max(N_list))
print(M * N // max(N_list))

다른 풀이

1)  유클리드 호제법 사용

아래와 같이 함수를 사용해서 풀어도 된다. 

import math

M, N = map(int, input().split())

# math.gcd는 유클리드 호제법을 사용하여 GCD를 빠르게 구합니다.
gcd_value = math.gcd(M, N)
lcm_value = M * N // gcd_value

print(gcd_value)
print(lcm_value)