[🥉1 / 백준 1145 / 파이썬] 적어도 대부분의 배수

 

1145번: 적어도 대부분의 배수

 

문제

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

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

입력

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

출력

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

 

예제 입력 1 30 42 70 35 90	예제 출력 1 210
예제 입력 2 1 2 3 4 5	예제 출력 2 4
예제 입력 3 30 45 23 26 56	예제 출력 3 1170
예제 입력 4 3 14 15 92 65	예제 출력 4 195

 

풀이

 

문제를 빠르게 해결하기 위해 수들의 최대공약수를 찾고, 다시 최대공배수를 반복하여 찾는 방식으로 풀 수 있다.

하지만 입력되는 수들의 최대 크기가 100으로, 매우 낮다.

따라서 그냥 숫자를 하나하나 올려가며 3개 이상의 수로 나누어 떨어지는지 확인하는 브루트 포스를 썼다.

다만, 숫자가 최대 크기가 1000 정도로만 되어도 아래 방법으로 풀이는 쉽지 않을 것이다.

 

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