백준 문제 풀이 - 적어도 대부분의 배수 1145번

📜 문제 이해하기

다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.
서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

💡 문제 재정의

5개의 숫자에서 적어도 3개의 배수를 찾아보자.

✏️ 계획 수립

모든 경우의 수의 3개 숫자 최소공배수를 구한 후 거기서 가장 작은 최소공배수를 출력한다.

💻 계획 수행

import math


def get_lcm(num1, num2):
    a = num1
    b = num2

    while b:
        a, b = b, a % b
    return (num1 * num2) // a


if __name__ == '__main__':
    num_list = list(map(int, input().split()))
    min_lcm = 100000000

    for i in range(5):
        for j in range(i + 1, 5):
            for k in range(j + 1, 5):
                lcm = get_lcm(num_list[i], get_lcm(num_list[j], num_list[k]))
                min_lcm = lcm if lcm < min_lcm else min_lcm

    print(min_lcm)

🤔 회고

최소공배수를 찾는 유클리드 알고리즘과 브루트포스를 사용하면 풀 수 있는 문제이다.