[백준] 1934번 최소공배수 - 파이썬(Python)

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

1934번: 최소공배수

 

문제

 

21.02.15 접근법

 

문제 그대로 최소공배수 구하면 된다.

최대공약수 구하고 각 수 곱해서 최대공약수로 나눠주기

 

 

21.02.15 코드

import sys

T=int(input())

for i in range(T):
    a,b=map(int,sys.stdin.readline().strip().split())
    aa,bb=a,b

    while bb!=0:
        aa=aa%bb
        aa,bb=bb,aa

    print(a*b//aa)

 

21.08.09 접근법

 

1. 최대공약수(GCD)를 유클리드 알고리즘으로 구하기

2. 입력 값들을 곱해 GCD로 나눠 최소공배수 구하기

 

유클리드 알고리즘은 아래 글에 설명되어 있음.

2021.08.09 - [코딩테스트 준비/백준] - [백준] 2609번 최대공약수와 최소공배수 - 파이썬(Python)

[백준] 2609번 최대공약수와 최소공배수 - 파이썬(Python)

 

 

21.08.09 코드

import sys

T=int(input())

for i in range(T):
    a,b=map(int,sys.stdin.readline().split())
    aa,bb=a,b

    while a%b!=0:
        a,b=b,a%b

    print(aa*bb//b)