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

풀이과정

최대공약수와 최소공배수를 푸는 단순 구현, 수학 문제이다.
위의 문제는 유클리드 호제법으로 간단히 풀 수가 있는데,
유클리드 호제법은 n과 m 이 있을 때(여기서 n은 m보다 큼) n과 m의 최대공약수 gcd는 m과 n % m의 최대공약수 gcd와 같다! 이다.

쉽게 말해 n을 m으로 나누어 떨어진다면 그때 m 이 최대공약수가 되고,
나누어떨어지지 않는다면 n은 m이 되고 m은 (n % m)이 된다.

다음과 같이 최대공약수를 찾았다면 기존 n, m을 곱한 값을 최대공약수로 나눠주면 최소공배수를 찾을 수 있다.

포인트

1. 먼저, 입력 받은 두 수(n, m)중 n이 m보다 커야한다. 때문에 n이 m보다 작다면 두 변수의 순서를 바꿔주는 코드가 필요하다.
   
   
2. n이 m으로 나누어 떨어진다면 그때 m을 출력한다.
   
   
3. 2번이 될 때까지 n은 m이 되고, n을 m으로 나눈 나머지를 m에 대입한다.
   
   
4. 다음과 같이 최대공약수를 찾은 후 입력받은 두 수를 곱한 값을 최대공약수로 나눠주면 최소공배수가 된다.

코드

n, m = map(int, input().split())
res = 0
r = -1   # 반복문 조건을 r != 0 으로 하기 위해 단순히 담은 값,,
lcm = n * m

while r != 0:
    if n >= m:   # 포인트 1번: n이 m보다 큰 수로 만드는 코드
        r = n % m
        if r == 0:   # 포인트 2번: n을 m으로 나눈 나머지값이 0이 될때 최대공약수는 m
            res = m
        else:   # 포인트 3번: 나누어 떨어지지 않을때 값을 다음과 같이 스위칭해준다.
            n = m
            m = r
    else:   # 포인트 1번: n이 m보다 큰 수로 만드는 코드
        tmp = n
        n = m
        m = tmp

print(res)
print(lcm // res)   # 포인트 4번