BAEKJOON_1934 "최소공배수" PYTHON

[백준] 1934번 Python 파이썬

 

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

1934번: 최소공배수

< 시간 초과 뜬 코드 >

for문을 이용하여 최소공배수를 구했더니 시간 초과가 떴다.

import sys

n = int(sys.stdin.readline())

result = 1
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    for j in range(max(a, b), a * b + 1):
        if j % a == 0 and j % b == 0:
            print(j)
            break

< 수정된 코드 >

유클리드 호제법을 이용하여 최대공약수를 구한 후 최소공배수를 구해주었다.

import sys

n = int(sys.stdin.readline())

for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    at, bt = min(a,b), max(a,b)
    while at % bt != 0:
        at, bt = bt, at % bt
    print((a*b)//bt)

 

 

혼자 공부하며 올리는 블로그입니다. 틀린 내용은 댓글 남겨주시면 감사하겠습니다.