사용자 도구

사이트 도구


ps:problems:boj:2014

문제제목

ps
링크acmicpc.net/…
출처BOJ
문제 번호2014
문제명소수의 곱
레벨골드 1
분류

우선순위큐

시간복잡도O(nmlognm)
인풋사이즈n<=100,000, m<=100
사용한 언어Python
제출기록51116KB / 268ms
최고기록224ms
해결날짜2022/05/01
태그

[라이] 우선순위 큐

풀이

  • 한번에 N번째 큰수를 바로 찾아낼 수 있는 방법은 없다. 소수의 곱으로 만들어질 수 있는 수들을 모두 만들어둔 다음에 그중에서 N번째 수를 찾아야 한다.
  • 소수의 곱으로 만들어질 수 있는 수는 무한개이다. 이중에서 N번째 이하가 될 가능성이 있는 수들만 어떤 휴리스틱으로 잘 추려내서 모은 뒤에 정렬하면 될거 같지만, 그렇게 타이트하게 걸러낼수 있는 휴리스틱을 찾기가 어렵다. 후보수의 갯수를 너무 넉넉하게 잡으려 하면 메모리 초과가 난다.
  • 처음에는 p[i]들로만 후보를 채우고, 후보 중에서 가장 작은 수 x를 찾아서 x*p[i]들을 후보에 추가하는 것을 반복하는 방식으로 푸는 방법이 떠올릴수 있는 가능한 방법이다. 이 과정을 N번 반복하면, N번째로 꺼낸 수가 답이 된다. 후보들을 우선순위 큐 (Priority Queue)로 관리하면 가장 작은수를 꺼내는 것과, 새로운 후보를 추가하는 것을 O(logn)에 할수 있다.
  • 신경써야 하는 부분은 같은 숫자가 후보에 두번 들어가는 것을 방지해야 하는 부분이다. 이를 위해서 추가로 set을 사용해서 중복을 관리하려고 했지만, 이 방법 역시도 메모리 초과에 걸렸다. 인터넷을 검색해서 더 알아낸 신박한 방법은 p[i]들을 순회하며 x*p[i]를 힙에 추가할때, x가 p[i]의 배수이면 거기서 종료하는 것이다. 이러면 후보에 추가되는 모든 수는, 그 수의 최소 소인수와 다른수의 곱으로 계산어질때에만 힙에 딱 한번 추가되게 된다. set을 추가로 사용할 필요가 없고, 힙에 추가하는 타이밍도 최대한 늦어지므로 힙 크기도 보다 작게 유지된다.
  • 중복을 제거하게 되므로, 힙에 추가되는 수의 갯수는 N*K보다는 많이 작을것 같은데, 수식으로 잘 계산을 못하겠다. 그냥 O(N*K)번이라고 치면, 총 시간복잡도는 O(NKlogNK)

코드

"""Solution code for "BOJ 2014. 소수의 곱".

- Problem link: https://www.acmicpc.net/problem/2014
- Solution link: http://www.teferi.net/ps/problems/boj/2014

Tags: [Priority queue]
"""

import heapq


def main():

    K, N = [int(x) for x in input().split()]
    primes = [int(x) for x in input().split()]

    heap = primes[:]
    heapq.heapify(heap)
    for _ in range(N):
        num = heapq.heappop(heap)
        for p in primes:
            heapq.heappush(heap, num * p)
            if num % p == 0:
                break
    print(num)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N X L T M
 
ps/problems/boj/2014.txt · 마지막으로 수정됨: 2022/07/08 01:42 저자 teferi