[Python/파이썬] 백준 19699번 소-난다!

19699번: 소-난다!

 

코드

from itertools import combinations

n, m = map(int, input().split())
h = list(map(int, input().split()))

prime = [True]*10000
for i in range(2, 10000):
    if prime[i]:
        for j in range(i*2, 10000, i):
            prime[j] = False
ans = set()
for comb in combinations(range(n), m):
    total = 0
    for c in comb:
        total += h[c]
    if prime[total]:
        ans.add(total)
if ans:
    print(*sorted(list(ans)))
else:
    print(-1)

 

N, M의 범위는 1 이상 9이하이므로 N마리의 소 중에 M마리를 뽑는 것은 어렵지 않다. 뽑은 소들의 무게의 합이 소수인가 판별하는 것이 포인트라고 생각한다.

 

소수를 판정하는 알고리즘으로는 '에라토스테네스의 체'이다. 이 알고리즘은 이름처럼 수를 체로 걸러내버린다. 무슨 말이냐면 소수인 어떤 수가 있을 때, 그 수의 배수들은 당연히 소수가 될 수 없다. 이 점을 이용하여 for문으로 2부터 원하는 범위까지 반복문을 돌며 소수인 수가 나오면 그 수의 배수들을 지워버리는(False로 만드는) 과정을 반복하는 방법으로 소수를 판정하는 것이 '에라토스테네스의 체'이다.

 

이렇게 범위 내의 모든 수를 돌며 소수가 될 수 없는 숫자들을 떨궈내고 나면 배열에 소수들 만이 남게된다.