[백준] 2609. 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

 

나의 풀이

1) 시간초과로 실패!

a, b=map(int, input().split())

for i in range(min(a,b),0,-1):  # 최대공약수
    if a%i==0 and b%i==0:
        print(i)
        break

for i in range(max(a,b),a*b+1): # 최소공배수
    if i%a==0 and i%b==0:
        print(i)
        break

 

최대공약수는 두 수의 공통 약수를 찾을 때까지 나누어주도록 했다.

for문을 짧게 끝내고 싶어서 큰 수부터 역순으로 내려가도록 range에서 -1로 설정해주었다.

최소공배수는 두 수 중 큰 수부터 두 수의 곱까지의 범위 내에서 공배수를 찾는 알고리즘이다.

 

짧은 코드인데 채점할 때 시간초과가 떠서 한동안 뭐지...뭐지...했다,,,아~~~놔

검색해보니 for문이 지나치게 많이 반복될 경우 시간초과가 뜰 수 있다고 해서

for문 하나를 아예 없애버렸다.

 

2) 최대공약수를 이용해 최소공배수 구하기

a, b=map(int, input().split())

gcd=0

for i in range(min(a,b),0,-1):
    if a%i==0 and b%i==0:
        gcd=i
        break

print(gcd)

lcm=a*b//gcd

print(lcm)

 

 두 수의 곱=최대공약수*최소공배수임을 이용했다.

더 예쁘게 짤 수 있었을 테지만 일단 여기서 만족 ^^;;

 

3) math모듈 사용하기

import math

print(math.gcd(a,b))
print(math.lcm(a,b))  # 파이썬 3.8 이하 버전에서는 안 돌아감. a*b//math.gcd(a,b)로 입력해주면 됨

 

웬만하면 알고리즘을 짜보려고 모듈을 이용하는 걸 지양하고는 있지만...

시간초과 때문에 여기에서는 한 번 써 봤다.

lcm은 파이썬 3.8 이하에서는 사용할 수 없는 기능이므로

에러가 뜨면 gcd를 구해준 후 2번 풀이와 같이 gcd를 이용하여 lcm을 구하면 해결~