요즘 계속 안 풀리는 문제들만 풀었는데, 오랜만에 쉬운거 두 개 풀어서 기분이 좀 좋았다,,,ㅎㅎ
그만큼 이번 문제도 쉬웠다는 뜻!
문제 해석
최대 공약수
문제를 풀기 위해 최대 공약수, 최대 공배수를 구하는 과정을 생각해봤다.
두 수 a,b(a<b)를 입력받았을 때 n으로 나눠주게 된다. 이 n은 1<n<=a 일 것이다. 왜냐하면 n=a가 될 수도 있기 때문이다.
1<n<=a
최대 공약수의 정의는 '두 수 이상의 여러 수의 공약수 중 최대인 수'라고 나와있다. 그런데 n<a로 정의한다면, a가 n으로 나눠질 수 있는데도 더이상 값을 구하지 않고 멈추게 된다. 최대 공약수의 정의에 벗어나는 계산이다.
2와 4를 예시로 생각해보면 간단하다. 1<n<a로 정의한다면 두 수의 최대 공약수는 1이 된다. 1<n<=a로 정이가 되어 있는 상황이라면, 두 수의 최대 공약수는 2가 된다.
최소 공배수
최대 공약수를 구했다면 최소 공배수를 구하는 것은 쉽다! 최대 공약수로 a,b를 나누고 나온 값들을 A,B라고 한다면 n x A x B를 하면 된다.
소스코드
def cal(a, b):
GCD = 1
LCM = 1
n = 2
while n <= a:
if a%n == 0 and b%n == 0:
a = a//n
b = b//n
GCD *= n
continue
n += 1
LCM = GCD * a * b
print(GCD)
print(LCM)
a, b = map(int, input().split())
if a > b:
a, b = b, a
cal(a,b)
소스코드 설명
계산을 해줄 cal이라는 함수를 정의하고, 그 안에서 최대 공약수와 최소 공배수를 구해줬다. 최대 공약수를 GCD, 최소 공배수를 LCM이라고 정의하고 각각 초기값을 1로 정의해줬다.
그런 다음 n<=a일 때까지 while문을 돌면서 a, b모두 나누어 떨어지는 n이 있을 때까지 계산을 하도록 했다. 둘 다 나누어 떨어지는 수 n이 발견되면 a와 b를 각각 n으로 나눈 값을 다시 a, b에 담고 GCD에 n을 곱해주었다.
while문을 빠져나온 뒤에는 LCM에 GCD x a x b를 한 값을 넣어준 뒤 각각 출력해줬다.
추가 궁금점
그런데 문제를 정리하면서 궁금해진 부분이,,,, 만약 최대 공약수가 1인 경우에는 어떻게 하지? 예를 들어 2와 7이 입력됐을 경우.. 나같은 경우엔 앞에서 n=2로 정의를 해놓았기 때문에 이런 경우 문제가 됐을텐데.. 흐음 백준 문제에서는 딱히 문제가 생기지 않았는데 그냥 백준에서도 이 부분을 놓친걸로 봐도 될까..?
