백준 1934번 풀이

문제

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

1934번: 최소공배수

주어진 두 수의 '최소공배수'를 출력하시오

 

Reference

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 나무위키

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

왜 뜬금없이 이게 나오는지는 보다보면 알게 된다.

 

풀이

자 일단 최소공배수가 뭐냐... 두 수 x, y가 있을 때 x의 배수이면서 y의 배수인 수 중 제일 작은 수가 최소공배수다. 이거 초등학생때 다 배운겁니다 여러분. 자매품으로는 최대공약수가 있는데 이건 x를 나눴을때도 나누어 떨어지고 y를 나누었을때도 나누어 떨어지는 제일 큰 수. 반대되는 개념은 왜 없냐면 최소공약수는 무조건 1이고 최대공배수는 수가 끝이 없어서 없다.

 

그리고 최대공약수/최소공배수 구할 때 어떻게 하냐...

저기서 왼쪽에 있는 2, 3만 곱하면 최대공약수(6)가 되고, 밑에 있는것(최종적으로 나온 몫)까지 다 곱하면 최소공배수다. 그래서 12와 18의 최대공약수는 6, 최소공배수는 36. 두 수가 서로소(공약수따원 없다네)일 경우 최대공약수가 1이기때문에 걍 깡으로 곱하면 그만이지만, 진짜 깡으로 곱해서 출력한다?

 

예~ 틀려요~

 

유클리드 호제법

그럼 여기서 저 유클리드 머시기가 왜 나왔는지를 알려주도록 하겠다. 유클리드 호제법은 자연수나 다항식의 최대공약수를 구하는 방법으로... 다항식에 그걸 써도 되는지는 모르겠으나 아무튼. 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 방식이라고 할 수 있다. 그래서 호제법이지 뭐 호형호제 이딴거 아님.

 

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 아, 글로 보면 모르겠죠?

출처: 나무위키-유클리드 호제법

미안... 이걸 손으로 쓰기엔... 이거 리눅스 놋북인걸... 프레스코따원 안된다규... 아무튼 이런 느낌이다. 그럼 예시를 몇 개 할짝여보고 가도록 하자. 참고로 나무위키에는 서로소의 예시가, 위키피디아에는 최대공약수가 존재하는 예시가 있다.

 

위키피디아에 있는 예시는 18696과 19332의 최대공약수를 찾는 것이다. 예시에 나온 두 수의 최대공약수는 36이다. 왜? 72를 36으로 나눠서 나머지가 0이 됐으니까. 그럼 두 수가 서로소면 어떻게 해요? 서로소인 13과 6의 예시를 들어보자면 13 = 6 * 2 + 1 -> 6 = 1 * 6 + 0 이기 때문에 둘은 서로소이고, 최대공약수가 1이 된다.

 

그럼 다시 풀이로 돌아가보자.

 

다시 풀이로

그러니까 유클리드 호제법으로 두 수의 최대공약수를 구한다는것까지는 알겠는데, 이걸로 뭘 할거냐고? 위 그림을 다시 보자. 18과 12의 최대공약수는 얼마? 6이다. 유클리드 호제법으로 18 12 하면 18 = 12 * 1 + 6, 12 = 6 * 2 + 0 해서 6 나온다. 그리고 어떻게 했어요? 18을 6으로 나눠서 나온 몫 3과 12를 6으로 나눠서 나온 몫 2를 곱했다 그죠?

 

import sys

def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

T = int(sys.stdin.readline())
for i in range(T):
    A, B = map(int, sys.stdin.readline().split())

위에 있는 함수는 위키피디아에 파이썬 예시로 있었던 코드다. 재귀형도 있긴 한데 그거는 공약수 있으면 뺑뺑이 도느라 시간초과 날 수 있으니 걍 함수형을 쓰자. 아무튼, 이 코드는 유클리드 호제법을 이용해 세 가지 단계를 거칠거다. 첫번째, 유클리드 호제법으로 최대공약수를 구한다. 두번째, 그 최대공약수로 A와 B를 각각 나눈다. 세번째, 몫 두 개랑 최대공약수를 곱한다.

 

import sys

def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

T = int(sys.stdin.readline())
for i in range(T):
    A, B = map(int, sys.stdin.readline().split())
    C = Euclidean(A,B) # 유클리드 호제법으로 최대공약수를 도출
    LCM = C * (A // C) * (B // C) # LCM이 최소공배수였다니 
    print(LCM)

그래서 A, B 입력받는 밑에 두 줄이 그거다. C는 유클리드 호제법으로 구한 최대공약수, 그리고 LCM은 최소공배수. 변수 할당하고 줄 늘리기 귀찮아서 걍 한큐에 곱해버였는데 //가 안 들어가면 뭐 된다? 소수점 됩니다. 그니까 // 쓰십셔. 아니면 int 드가야되는데 귀찮기도 하고, 어차피 우리는 몫만 필요하니께(나머지가 없기도 함). 그래서 A // C는 A를 C로 나눈 몫, B // C는 B를 C로 나눈 몫이다. 그리고 C와 몫 두 개를 곱하면 LCM, 최소공배수가 된다.

 

밑에 있는 print문은 말 그대로 최소공배수 출력하라는 얘기. 변수 할당할 필요 없이 print문에 저 식 때려박아도 되긴 되는데 그렇게 하면 틀렸을때 수정하다가 머리터짐.... 한큐에 맞춰서 망정이지.