[Python] 백준/BOJ 19699번: 소-난다! (Silver 2)

💻 Problem

문제 보러 가기

 

농장에는 N마리의 소가 있다. 농부 존은 소들의 몸무게의 합이 소수(prime)가 되도록 M마리의 소를 선별할 계획이다. 농부 존의 계획에 맞게 소를 선별했을 때 나올 수 있는 몸무게의 합을 모두 출력하시오.

 

💡 Approach

전체 로직

1. 조합으로 m마리의 소를 뽑아 후보 리스트에 저장한다.
2. 후보를 하나씩 살펴본다.
   1. 몸무게의 합을 구해 몸무게의 합이 소수이면 정답 리스트에 추가한다.
3. 정답 리스트를 정렬해서 출력한다. (비어있으면 -1 출력)

 

소수 판정 로직

1. target이 1이면 소수가 아니다.
2. target에서 2부터 √ target까지의 값 중 나눠지는 숫자가 있으면 소수가 아니다.
3. 1, 2에서 걸리지 않았으면 소수이다.

 

소수 판정 로직의 2번에서 반복문의 범위가 2 ~ √ target인 이유는 target의 약수가 √target을 기준으로 대칭적으로 존재하기 때문이다.

 2 ~ target으로 범위를 잡아도 답은 나오지만, target의 약수는 항상 √target을 기준으로 쌍을 이루기 때문에 √target까지만 검사해도 된다.

헷갈린다면 직접 임의의 숫자의 약수를 구해보고 그 중간에 √임의의 숫자를 넣어보면 이해될 것이다.

 

✏️ Solution

import sys
from itertools import combinations
input = sys.stdin.readline

def is_prime(target):
    if target == 1:
        return False
    for i in range(2, int(target ** 0.5) + 1):
        if target % i == 0:
            return False
    return True

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

# m마리의 소를 뽑아 몸무게 합 구하기
candidates = list((combinations(h, m)))

for candidate in candidates:
    total = sum(candidate)
    # 몸무게의 합이 소수이면 저장
    if is_prime(total):
        ans.add(total)

print(' '.join(map(str, sorted(ans))) or -1)

 

⏱️ 시간복잡도

• 조합 생성: nCm
• 소수 판별: √(m * max(h))