문제

해석

5개의 수가 주어짐. 3개를 뽑아서 최소공배수를 구하는데, 가장 작은 최소공배수를 찾으라는 말임.

문제 분석

쉬운 난이도 문제인 만큼, 숫자의 범위가 그렇게 빡빡하지 않음. 주어지는 숫자들도 100보다 작거나 같은 자연수고, 고작 5개임.

5개중 3개를 뽑는 모든 경우의 수에서 각 수의 약수들을 조합해 최소 공배수를 구하면 좋겠다 싶었음.

구현

내부 라이브러리 import

from itertools import combinations
from collections import defaultdict

5개중 3개를 뽑으니 combinations을 활용했고,
dict을 통해서 약수들을 할건데 한개도 없는 경우 default 값을 0으로 하고 싶어서 편의상 defaultdict을 사용함.

100 이하의 소수 전부 구하기.

primes= dict()
primeNum = []
for i in range(2,101):
    if i not in primes:
        primes[i] = True
        primeNum.append(i)
        for j in range(i*2, 101,i):
            primes[j] = False

약수는 소수들의 곱으로 이루어져있기 때문임.

약수 구하는 함수 구현

def getDivisor(n, primes):
    result = defaultdict(int)
    
    for d in primes:
        
        while n % d == 0:
            result[d] += 1
            n = n//d
            
    return result

primes는 바로 위에서 구한 소수들의 집합임.

수행부분 구현

# 5개의 수를 입력받음.
nList = list(map(int,input().split()))

# 결과값. 최소값을 구해야하니 아주 큰 값으로 초기화해줌.
answer =10e10

# list(combinations(nList,3))으로 5개의 값중 3개를 뽑은 combinations을 만들고 그걸로 loop를 돌았음.
for combi in list(combinations(nList,3)):
    
    # 최소공배수들의 약수가 저장될 곳
    result = defaultdict(int)
    
    # combi는 5개중 3개를 뽑은 그 케이스의 3개의 숫자의 수열임.
    for n in combi:
    	# getDivisor(n) 으로 n의 모든 약수를 구함. 
        temp = getDivisor(n)
        
        for ti in temp:
        	# n의 약수가 곱해진 최대값을 구함.
            result[ti] = max(result[ti] , temp[ti])
    
    # 실제 최소공배수를 구할 것이므로 초기 값은 1로 초기화
    tempAnswer = 1
    
    # 최소 공배수들의 약수와 약수의 개수로 최소 공배수 구함.
    for rn in result:
        tempAnswer *= (rn ** result[rn])
    
    # 현재 조합의 최소공배수와 기존에 구한 answer 값 비교해서 answer값이 더 작은 족에 대입.
    answer = min(tempAnswer, answer)
    
print(answer)

결과

성공.