[브루트포스/수학] 백준 1145 거의 대부분의 배수 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

 

2. 문제 풀이

 서로 다른 5개의 숫자가 주어집니다. 적어도 3개 이상의 수가 약수로 포함되는 최소의 수를 찾아야 합니다.

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 5개 중에서 3개를 뽑아서, 모두 곱한 다음 최소인 수를 고르면 되겠지? 하면 틀립니다. 예제 입력 2를 보면 1, 2, 3, 4, 5 중 1, 2, 4를 선택하면 8이 아니라, 4입니다.

 따라서 수학적으로 접근하려 하지말고, 무식하게 찾는 게 오히려 빠르고 쉽습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
numlist = list(map(int, input().split()))

# 약수가 3개 이상인 수 찾기
num = 2
while True:
    cnt = 0
    for i in numlist:
        if num % i == 0:
            cnt += 1

    if cnt >= 3:
        print(num)
        break
    num += 1

 2부터 1씩 올리면서, 약수가 3개 이상인 수를 찾습니다.