백준 2014 소수의 곱 C++

https://www.acmicpc.net/problem/2014

2014번: 소수의 곱

주어진 소수의 곱으로 만든 수열 중 N번째 수를 구하는 문제입니다. 간단한 문제이지만 아이디어를 생각하는데 꽤 걸렸습니다. (시험 공부하기 싫어서 푼 문제인데 생각보다 너무 오래걸렸다.....)

 

우선순위 큐를 오름차순 (top이 가장 작은 값)으로 설정 후 다음의 단계를 거치면 됩니다.

1. 큐의 top값을 주어진 수들과 곱한다. 그리고 pop한다.

2. 큐의 크기가 N보다 크고 큐의 가장 큰 값이 곱한 값보다 작으면 큐에 넣지 않는다.

3. 이미 계산된 결과면 넣지 않는다.

4. 나머지는 넣는다.

 

이 과정을 거치면 N번 수행 시 큐의 top값이 원하는 결과입니다.

 

예시를 이용하면 k=4, n=6, 소수 =  2 3 5 7 입니다. (n=19는 커서 n=6로 합시다. n=6이면 정답은 7입니다.)

큐에 1이 들어있는 상황이라면

 

n = 1 : top : 1 => pop => 큐 size = 0 => 큐 <- 2, 3, 5, 7 , 큐 : 2 3 5 7

n = 2 : top : 2 => pop => 큐 size = 3 => 큐 <- 4, 6, 10, 14, 큐 : 3 4 5 6 7 10 14

n = 3 : top : 3 => pop => 큐 size = 6 => 큐 <- 9, 15, 21 (6은 패스) , 큐 : 4 5 6 7 9 10 14 15 21

n = 4 : top : 4 => pop => 큐 size = 8 > n => 큐 <- 8, 12, 20 (28은 큐의 최댓갑 21보다 큼) => 

큐 : 5 6 7 8 9 10 12 14 15 20 21

n = 5 : top : 5 => pop => 큐 size = 10 > n => 큐 <- X (10, 15는 이미 사용, 25, 35는 21보다 큼)

=> 큐 : 6 7 8 9 10 12 14 15 20 21

n = 6 : top : 6 => pop => 큐 size = 9 > n => 큐 <- 18 (12는 이미 사용, 30, 42는 21보다 큼)

=> 큐 : 7 8 9 10 12 14 15 20 21

 

그러므로 남은 큐의 top = 7이고 이는 6번쨰 수입니다.

 

코드는 다음과 같습니다.