테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 문제제목 ======

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


===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_1}}