---
title: "알고리즘 공부"
excerpt: "백준 ; 최소공배수"
permalink: /algorithms/37

categories:
  - algorithms
tags:
  - programmers
  - algorithms
  - python
last_modified_at: 2020-08-06
---
최소공배수  
<https://www.acmicpc.net/problem/1934>
처음엔 막무가내로 최소공배수를 구하려다 시간 초과가 됐다
정답은 나머지를 찾고 찾아 그게 0이라면 a를 아니라면 나머지 리턴하는 것
시간초과된 풀이  
```python
T = int(input())
for _ in range(T):
    A, B = map(int, input().split())
    if A>B:
        A,B=B,A
        
    i = int(1)
    while i<B*A:
        if((B*i)%A==0):
            print(B*i)
            break
        else:
            i+=1
```
정답 풀이
```python
def lcm(a,b):
    d = gcd(a,b)
    return d*(a//d)*(b//d)
def gcd(a,b):
    return gcd(b%a,a) if b%a else a
T = int(input())
for _ in range(T):
    A, B = map(int, input().split())
    if A>B:
        A,B=B,A
    print(lcm(A,B))
```
소요시간 ; 40분
함수 쓰는 법 알고 자유자재로 쓰도록 연습하자