[백준]🥉1145 : 적어도 대부분의 배수

문제 설명

다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.

서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.

출력

첫째 줄에 적어도 대부분의 배수를 출력한다.

 

num = list(map(int, input().split()))
N = 1
while True:
    cnt=0
    for i in num:
        if N%i == 0:
            cnt+=1
    if cnt >= 3:
        print(N)
        break
    N+=1

 

❌ 오답 접근: LCM(최소공배수) 구하기

어떤 3개의 조합을 골라도 최소공배수는 모두 매우 큽니다.

• 예: 2, 3, 5 → LCM = 30
• 2, 3, 7 → 42
• 5, 7, 11 → 385 ...
• 그런데 공통 배수는 LCM 외에도 더 작은 수일 수 있음.

또한 문제는 세 수의 최소공배수 중 최소값을 구하는 게 아니라,
"1부터 시작해서 특정 수가 3개 이상의 수의 배수인지"를 찾는 것입니다.

✅ 정답 접근법 (브루트포스)