백준 - 2609. 최대공약수와 최소공배수(MJ)

#2609. 최대공약수와 최소공배수

백준의 브론즈1티어 문제이다.

📖Problems

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

6
72

🔍Approach

1.  최대공약수 구하는 법
   • 유클리드 호제법을 통해 최대공약수를 쉽게 구할 수 있다.
   • 유클리드 호제법으로 최대공약수를 구하는 방법은 다음과 같다.

   • 두 자연수 a, b에 대하여 a를 b로 나눈 나머지 temp에 대해 a와 b의 최대공약수는 b와 temp의 최대공약수와 같다. 이를 계속 반복하며 b=0이 될 때, a값이 바로 최대공약수이다. (재귀와 반복이 느껴진다..!!)

       while b > 0 :
           tmp = a % b
           a = b
           b = tmp
       return a
     

2. 최소공배수 구하는 법

• gcd는 a와 b의 최대공약수이다. x와 y는 서로소 관계라고 할 때,
• 입력값인 두 정수 a, b에 대하여  **a = x * gcd , b = y * gcd** 이므로 최소공배수는 a*b // gcd가 된다..!!

🚩My submission

Flow

1. 입력받기
2. gcd와 lcm은 각각 최대공약수와 최소공배수를 의미하며 0으로 초기화한다.
3. gcd 를 n을 m으로 나누었을 때의 나머지를 최대공약수에 저장하고, n과 m, gcd를 바꾸어가며 반복적으로 연산을 수행한다.
4. 3은 n % m이 0이 아닐 때 반복한다.
5. lcm은 n값과 m값을 곱한 값에 최대공약수 gcd를 나눈 값이다. 해당 연산을 수행한다.
6. 이후 gcd, lcm 순으로 출력한다.

n, m = map(int, input().split())
gcd, lcm = 0, 0
n2, m2 = n, m
# 최대공약수 = gcd, 최소공배수 = lcm
while n % m != 0:
    gcd = n % m
    n = m
    m = gcd

lcm = (n2 * m2) // int(gcd)

print(gcd)
print(lcm)

» 런타임 에러 (ZeroDivisionError)

어째 한번에 맞는 게 없냐…

🚩Others submission

참고 사이트 : https://animoto1.tistory.com/entry/백준-2609-최대공약수와-최소공배수

일단 함수화 시켜보자

위에서 작성한 코드를 함수로 변환한다.

import sys
input = sys.stdin.readline
a,b = map(int,input().split())

def gcd_r(a,b) :
    if b == 0 :
        return a
    else :
        return gcd_r(b,a%b)

def gcd_for(a,b) :
    while b > 0 :
        tmp = a % b
        a = b
        b = tmp
    return a

def lcm(a,b) :
    return a*b//gcd_r(a,b)

print(gcd_r(a,b))
print(lcm(a,b))

💡TIL

• 최대공약수와 최소공배수는 초등학교 때 배운 것인데 성인되니 다 까먹었다. 하지만 이 문제를 통해 최대공약수와 최소 공배수의 규칙을 찾고 코드로 구현시켰다. (일종의 공식처럼 코딩에서 사용되고 있다)
  1.  최대공약수 구하는 법 (유클리드 호제법)

     • 두 자연수 a, b에 대하여 a를 b로 나눈 나머지 temp에 대해 a와 b의 최대공약수는 b와 temp의 최대공약수와 같다. 이를 계속 반복하며 b=0이 될 때, a값이 바로 최대공약수

         while b > 0 :
             tmp = a % b
             a = b
             b = tmp
         return a
       

2. 최소공배수 구하는 법

• gcd는 a와 b의 최대공약수이다. x와 y는 서로소 관계라고 할 때,

• 입력값인 두 정수 a, b에 대하여  **a = x * gcd , b = y * gcd** 이므로 최소공배수는 a*b // gcd가 된다.

• 또 한 번에 여러 ‘연산’을 사용해야 할 경우, 함수를 사용하는 것이 더 편하다.