haju__log

[python][백준/BOJ] 1934번 : 최소공배수 본문

BOJ_백준

[python][백준/BOJ] 1934번 : 최소공배수

haju 2023. 3. 10. 17:27
반응형

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

 

1934번: 최소공배수

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있

www.acmicpc.net

 

t=int(input())

for _ in range(t):
    a,b=map(int,input().split())
    for i in range(max(a,b),a*b+1):
        if i%a==0 and i%b==0:
            print(i)
            break

✅==> 이렇게 풀었는데 시간초과됨 ㅎ

반응형

✅==>수정된 버전! <유클리드 호제법>

 

t=int(input())

for _ in range(t):
    a,b=map(int,input().split())
    aa,bb=a,b

    while a%b!=0:
        a,b=b,a%b
    print(aa*bb//b)
반응형

'BOJ_백준' 카테고리의 다른 글

[python][백준/BOJ] 10989번 : 수 정렬하기 3 (메모리 초과 해결)  (0) 2023.06.12
[python][백준/BOJ] 10815번 : 숫자 카드  (0) 2023.06.12
[python][백준/BOJ] 10988번 : 팰린드롬인지 확인하기  (0) 2023.03.10
[python][백준/BOJ] 9506번 : 약수들의 합  (0) 2023.03.10
[python][백준/BOJ] 9010번 : 사분면  (0) 2023.03.10
'BOJ_백준' Related Articles more