백준 [1934.최소공배수] | Python

✏️ 문제

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

1934번: 최소공배수

 

✏️ 풀이방법

- 앞서 풀어본 2609번의 최대공약수와 최소공배수 소스코드를 제출했다가 바로 시간초과가 떴다. 2609번 문제는 범위가 10,000이하의 자연수이지만 1934번은 45,000만큼의 수이다. 

1. 소인수분해를 이용해서 풀이를하면 굉장히 많은 반복이 필요하기 때문에 시간초과가 발생한다.

2. 유클리드 호제법을 이용해서 풀이했다.

 

 

📌 코드

t = int(input())
ab = [list(map(int,input().split())) for _ in range(t)]
for l in range(t):
    a = ab[l][0]
    b = ab[l][1]
    while True:
        remain = a%b
        if remain == 0:
            break
        a = b
        b = remain

    lcm = (ab[l][0]*ab[l][1]//b)
    print(lcm)

 

📌 결과

#입력
3
1 45000
6 10
13 17

#출력
45000
30
221

 

 

🤔 시행착오.1

t = int(input())
ab = [list(map(int,input().split())) for _ in range(t)]
for i in ab:
    for j in range(2):
        print(ab[i][j])

    print(ab[i][j])
          ~~^^^
TypeError: list indices must be integers or slices, not list

- 첫번째 for문의 i에 ab리스트를 담았는데 print문의 인덱스로 i를 담아서 인덱스안에 리스트를 출력하려고해서 발생한 에러

 

 

 

🔎 다른풀이

def gcd(x, y):  #최대공약수 구하기
  if y == 0:
    return x
  else:
    return gcd(y, x%y)
  
def lcm(x, y):  ## 최소공배수 구하기
  result = (x*y) // gcd(x,y)
  return result

num = int(input())

for i in range(num):
  x, y = map(int, input().split(" "))
  print(lcm(x, y))
  
  - https://goplanit.site/

-  유클리드 호제법을 재귀함수로 구현

 

 

📝 메모

- 유클리드 호제법

 

 

 

📒 다시보기

2024.01.29 - [Online judge/baekjoon] - 백준 [2609.최대공약수와 최소공배수] | Python

백준 [2609.최대공약수와 최소공배수] | Python