BOJ_2014 소수의 곱

• TOC {:toc}

이 글은 백준 온라인 저지의 2014번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2023.02.28

우선순위 큐 구현 때문에 파이썬으로 풀이

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N, K = map(int, input().split())
primes = list(map(int, input().split()))

def main():
    heap = primes[:]
    head = primes[0]
    for i in range(K):
        head = heappop(heap)

        for prime in primes:
            heappush(heap, head * prime)
            if head % prime == 0:
                break
    return head

print(main())

아이디어 & 풀이

매번 소수 중 최솟값을 구해야하기 때문에 힙(우선순위 큐)을 이용한다.

• 주어진 소수로 초기값을 정의한 후
• 최솟값을 pop한 뒤 해당 소수에 주어진 소수들을 곱한 값을 heap에 push한다.

이 때, 값이 중복으로 들어갈 수 있는데 실행 속도를 위해 이를 방지하는 게 좋다.

• 예를 들어 head가 2일 때 각 prime을 곱해서 나오는 6(2x3), 10(2x5), 14(2x7)은 각각 head가 3, 5, 7일 때 prime 2를 곱해도 얻을 수 있다.
• 두 경우 중 한 경우만 push할 수 있도록 조건을 지정해주어야 한다.

위의 경우에서는 head의 “기저값”이 prime보다 큰 경우에만 push하도록 해주고 있다. 표로 나타내면 다음과 같다.

• 대각선을 기준으로 왼쪽 하단의 값은 집어넣지 않고 오른쪽 상단의 값만 집어넣어야 한다.
• 설명한 그대로 수를 집어넣고 넣지 않는 기준은 표의 대각선에 해당하는 값들로 head와 prime이 같은 경우이다.
• 즉, 해당 값을 집어넣은 뒤 자기 자신으로 나눴을 때 나누어 떨어지면 반복문을 break 하면 된다.
  • 주어진 값들은 소수이므로 공유하는 약수가 없어 각 값이 나누어 떨어지는 경우는 자신으로 나눴을 때 밖에 없다.

위에서 “기저값”이라고 한 이유는 각 수의 곱들로 이루어진 경우에도 동일하게 적용할 수 있기 때문이다.

• 예를 들어 head가 4(2 x 2)인 경우 추가할 수 있는 값은 8(4 x 2), 12(4 x 3), 20(4 x 5), 28(4 x 7)이다.
• head가 2일 때와 같이 12, 20, 28은 각각 head가 6(3 x 2), 10(5 x 2), 14(7 x 2)일 때 prime 2를 곱해 추가되므로 추가할 필요가 없다.
  • head2에 2가 곱해서 4가 만들어 졌다면 당연히 주어진 3, 5, 7에 2가 곱해져 6, 10, 14도 만들어진다.
• 즉 이는 위의 표의 head 값에 2를 곱한 경우와 동일하며 동일한 원리를 적용해서 중복을 방지할 수 있다.
  • 2가 곱해진 수여도 나누어 떨어지는 경우는 동일하다.

이를 일반화해서 표현하면 각 prime 값을 순회하면서 값을 추가한 뒤 해당 prime 값으로 나누어 떨어질 때 반복을 break 한다.

for prime in primes:
    heappush(heap, head * prime)
    if head % prime == 0:
        break