[python_파이썬_pass]백준_13241번_최소공배수_풀이

공부하는허딩크 : https://www.youtube.com/live/Po-wyZ1d0yg?feature=shared

바로 직전에 1934번 최소공배수 문제를 풀었으면 금방 풀 수 있다. > 문제중 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오? 이게 무슨말이지??? 파이썬은 c언어처럼 변수의 크기를 할당하는게 없을텐데?'' 파이썬에는 해당 없음.

 

★공배수 관련 정리 : https://heodinkcodingdiary.tistory.com/56

[python_파이썬_공배수 시간복잡도_유클리드호제법]백준_1934번_최소공배수_풀이

 

<첫번째 시도 : 맞았습니다. _ 44ms>

바로 math.gcd함수로 최대공약수를 구하면서 A * B에 나눠주면 최소공배수가 나온다.

import sys

import math

input = sys.stdin.readline

A, B = map(int, input().split())

print(A * B // math.gcd(A, B))

 

<두번째 시도 : 맞았습니다. _ 240ms>

유클리드호제법이 아닌 큰 수의 약수를 구해주고(A) 그 약수들 중에서 B와 나눴을때 나머지가 0이 되는 가장 큰 수를 구하면 그게 최대 공약수가 된다. 

import sys

import math

input = sys.stdin.readline

A, B = map(int, input().split())

A, B = max(A, B), min(A, B)

A_list = [i for i in range(1, A + 1) if A % i == 0]

A_list.sort(reverse=True)

for i in A_list:

    if B % i == 0:

        answer = i

        break

print(A * B // answer)

 

<세번째 시도 : 맞았습니다._ 40ms>

유클리드호제법으로 해결했다.

import sys

import math

input = sys.stdin.readline

A, B = map(int, input().split())

a, b = max(A, B), min(A, B)

if a >= b:

    a, b = b, a

while b != 0:

    a, b = b, a % b

print(A * B // a)

 

<다른사람 풀이 참고>

gcd함수와 lcm함수를 생성 후 lcm함수만 돌리는 것도 괜찮은 것 같다.

def gcd(x, y):

    while y:

        x, y = y, x % y

    return x

def lcm(x, y):

    return (x * y) // gcd(x, y)

a, b = map(int, input().split())

print(lcm(a, b))