[백준] 11688번: 최소공배수 찾기 - 파이썬

🔈 문제

세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다.

 

📝입력

첫째 줄에 a, b, L이 주어진다. (1 ≤ a, b ≤ 106, 1 ≤ L ≤ 1012)

 

📑출력

첫째 줄에 c를 출력한다. 만약, 가능한 c가 없으면 -1을 출력한다.

 

📚 문제 해석

이전에 풀었던 최대 최대 최소공배수 찾기 문제와 비슷한 유형같아서 풀어보았다.

이번 문제는 a와 b 그리고 L 이 주어질 때 lcm(a,b,c) == L 을 만족하는 c의 최소값을 구하면 된다.

 

처음에 미리 a와 b의 최소공배수를 구한 다음 while 문을 돌려서 c의 값을 하나씩 올려 L을 찾았는데, TLE 판정 받았다.

그래서 c += 1 이 아닌 c += lcm(a,b)//10 을 하였는데도 TLE 판정 받았다.

다른 분의 코드를 보니 c *= L//lcm(a,b) 이 맞는 알고리즘이었다.

 

여러번 TLE 받고 다른 방법을 찾기 시작하였다.

약간의 고민 끝의 찾은 방법은 이것이다.

L의 약수를 모두 찾고 오름차순 정렬하여 하나씩 넣어보는 것이다. L의 약수를 찾을 때는 처음부터 끝까지 돌려버리면 이때도 시간초과 판정을 받을 것이다. 그래서 제곱근까지 돌려 시간복잡도를 O(sqrt(n))로 설계하여 약수를 찾았다.

L의 약수리스트를 만들고 lcm(ab, c) == L 인 것을 찾았다. (이때 c는 약수리스트의 데이터)

 

 

[백준] 25432번: 최대 최소공배수 - 파이썬

 

💻 코드

import math

a,b,L = map(int,input().split())

def divisor(n): # L의 약수리스트 만들기
    can = []
    for i in range(1, int(math.sqrt(n))+1): # 제곱근까지만 돌림
        if n%i==0: # 약수라면
            can.append(i)
            can.append(n//i)
    return sorted(can) # 정렬


if math.lcm(a,b) == L: #a와 b의 최소공배수가 이미 L이라면 c는 1
    print(1)
elif L%math.lcm(a,b)!=0: # lcm(a,b,c) ==L 이 될수 없다면 -1 출력
    print(-1)
else:
    ab = math.lcm(a,b)
    for c in divisor(L): # L의 원소리스트
        if math.lcm(ab, c)==L: # 만족한다면
            print(c) # c 출력후 종료
            break

 

🍭 시행착오

메모리 늘어나고 시간 늘어난 코드는 우선순위 큐를 사용하여 원소리스트를 만들어준 코드인데, 오히려 역효과가 났다.

 

🔗 문제링크 최소공배수 찾기

11688번: 최소공배수 찾기