[백준] 13241번 : 최소공배수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

13241번: 최소공배수

 

1. 문제 설명

2. 풀이과정

해당 문제는 두 수의 최소공배수를 구하는 문제이다.

두 수의 최소공배수는 두 수의 공약수의 곱에 각 수를 두 수의 공약수의 곱으로 나눈 몫을 곱한 값이다.

ex) 6, 8 → 공약수 = 2 → 2 × (6 / 2) × (8 / 2) → 24

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 최소공배수를 구할 두 수를 입력받는다. A, B = map(int, sys.stdin.readline().split())
3. 공약수의 곱을 저장할 변수를 생성하고 1로 초기한다. MAX = 1
4. 약수를 저장할 변수를 생성하고 2로 초기화한다. i = 2
5. 나누는 약수가 나누어지는 수보다 작으면 반복한다. while (A >= i) and (B >= i)
6. 만약에 해당 약수가 두 수의 공약수라면 if (A % i == 0) and (B % i == 0)
7. 해당 약수를 공약수의 곱에 곱한다. MAX *= i
8. 각 수를 약수로 나눈 몫의 결과로 다시 저장한다. A //= i  B //= i
9. 반면에 공약수가 아니면 else
10. 해당 약수를 1 증가시켜 다음 수를 약수로 정한다. i += 1
11. 최소공배수는 공약수들의 곱과 각 수를 해당 수로 나눈 몫을 각각 곱한 결과이다. print(MAX * A * B)

반응형

3. 소스코드

import sys

A, B = map(int, sys.stdin.readline().split())

MAX = 1
i = 2
while (A >= i) and (B >= i):
    if (A % i == 0) and (B % i == 0):
        MAX *= i
        A //= i
        B //= i
    else:
        i += 1

print(MAX * A * B)