[알고리즘] 백준 2609 (파이썬 풀이)

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

문제

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

입력

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

출력

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

해결코드

import sys

n,m = map(int, sys.stdin.readline().split())
a,b = n,m
while(b!=0):
    a = a%b
    a,b = b,a
print(a)    
print(n*m//a)

문제풀이

이 문제는 최대공약수와 최소공배수를 구하는 문제이다.

간단하게 생각하고 풀었는데 계속해서 시간초과가 나서 다른 방법을 써야겠다고 생각했다.

유클리드 호제법을 이용하면 일단 최대공약수를 구할 수 있다.

처음에 a,b에 n,m값을 대입하고

a에는 a를b로 나누었을 때 나머지 값을 대입

그다음 그 값을 b에 넣고 a에는 원래의 b값을 대입한다.

그렇게 서로가 서로를 계속 나누다 보면 b가 0이 되는 시점(a를b로 나누었을때 나누어떨어지는 시점)

에서 a의 값을 최대 공약수가 된다.

최소 공배수는 원래의 n,m을 곱하고 최대 공약수로 나누어 주면 최소 공배수가 된다.