[BEAKJOON] 백준 2609번 : 최대공약수와 최소공배수

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

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

 

문제 설명

 

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

 

풀이 코드

 

나는 처음에 input으로 a, b를 입력 받고,

둘중에 큰 값을 확인한 후,

최대공약수는 가장 정석적인 방법으로, 최소공배수는 당시에 풀때는 자각하지는 못했지만, 유클리드 호제법으로 접근을 했다.

최대공약수를 먼저 구해서, 최대공약수에 대한 정보를 안 상태로 최소공배수와 연관성을 가지고 있지 않을까에서 시작된 접근법이었다.

import sys
input = sys.stdin.readline

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

if(a>b):
    c = b
    d = a
else:
    c = a
    d = b

for i in range(c, 0, -1):
    if((a%i==0) & (b%i==0)):
        min = i
        print(min)
        break
        
print(((a//min) * (b//min))*min)

근데, 만일 최대공약수에 대한 정보가 없는 상태라면,

for i in range(d, (a*b)+1):
    if ((i % a == 0) & (i % b == 0)):
        print(i)
        break

 

이렇게 해줄 수 있다!

 

그리고 뿐만 아니라 유클리드 호제법도 존재한다.

유클리드 호제법

 

유클리드 호제법의 정리는 다음과 같다.

두 수 a, b ∈ ℤ 이고, r = a mod b 이라고 한다. (r 은 a에 b를 나눈 나머지를 의미)
이 때 r은 (0 ≤ r < b) 이고, a ≥ b 이다.

이 때 a 와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다.

즉, 아래와 같다는 의미다.

GCD(a, b) = GCD(b, r)

 

유클리드 호제법을 사용한 코드

a, b = map(int, input().split())
# c, d = a, b
# while b > 0:
#     a, b = b, a % b
# print(a)
# print(c*d//a)