[BOJ][Python]백준 2609번 풀이

그냥 듀크입니다. 이번에는 유클리드 호제법을 사용해서 풀어봅시다.

 

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

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

코드 : 

import sys
ssr = sys.stdin.readline

def gcd(n,m):
    if n%m == 0:
        return m
    else:
        return gcd(m,n%m)

a,b = map(int, ssr().split())
if a<b: a,b=b,a
g = gcd(a,b)
print(g)
print(int(a*b/g))

유클리드 호제법은 이름에서도 알 수 있듯이 유클리드(에우클레이데스)라는 수학자가 만든 방법입니다. 인물 소개는 넘어가고 호제법이란 방법에 대해서 잠깐 알아보면,

호제법이란 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.(출처 : 위키백과)

최대공약수를 구하는 알고리즘이라고 알고 계시면 됩니다. 수학적 증명이 어떻게 되는지는 모르지만 일단 저희는 문제를 풀기 위해서 이 방법을 쓸 줄은 알아야겠죠. 정말 간단하게 코드로 구현할 수 있습니다.

 

최소공배수의 경우 주어진 두 수의 곱에서 최대공약수를 나누면 바로 구할 수 있습니다.

 

어째 이번 주까지 골드를 찍겠다고 다짐을 했는데 이것저것 하다보니 목표를 이루지 못했습니다. 당초에 올 해까지 이루려 하던걸 무리하게 앞당겨서 그런지는 모르겠으나 어쩔 수 없이 다음 주까지 또 백준만 파는 삶을 살게 되겠네요.

 

그냥 듀크였습니다.