[백준, 파이썬, 1934번] 최소공배수

 

풀이

• 처음 접근한 방법은 a,b 가 같아질 때까지 값을 더하는 방식으로 풀었지만
  • python은 시간초과
  • pypy는 제출 성공
• 그래서 문제의 아래를 확인해보니 유클리드 호제법이 있어서 확인한 다음 풀이
  • 최소 공배수를 찾기위해선 최대 공약수를 먼저 계산한 다음 풀이
  • 최대 공약수는
    • a,b = b, a%b 로 b가 0이 될 때까지 구한 a의 값
  • 최소 공배수는 
    • a*b // 최대공약수

 

정답 코드

# 유클리드 호제법

import sys

input = sys.stdin.readline

for _ in range(int(input())):

    a,b = map(int,input().rstrip('\n').split())

    result = a*b

    if b>a: a,b = b,a

    while b != 0:

        a,b = b, a%b

    print(result//a)

 

pypy만 제출된 코드

import sys

input = sys.stdin.readline

for _ in range(int(input())):

    a,b = map(int,input().rstrip('\n').split())

    c_a,c_b = a,b

    while c_a != c_b:

        if c_a > c_b: c_b += b

        else: c_a += a

    print(c_a)