[백준 2014번] 소수의 곱

난이도: 골드 2

문제 링크: www.acmicpc.net/problem/2014

2014번: 소수의 곱

문제 2014: 소수의 곱

언뜻 봐서는 어려워 보이는 수 관련 문제입니다.

문제 분류는 수학, 자료 구조, 정수론, 우선순위 큐라고 하네요.

 

얼핏 생각하면 다소 어려운 문제이긴 합니다.

숫자에 곱셈을 하는 정해진 횟수가 존재하지 않다 보니,

2, 2*2, 2*2*2, 2*2*2*....*2 등도 존재할 수 있기 때문에, 곱을 얼마나 해야 할지 감이 오질 않았어요.

 

고민 끝에 제가 시도한 접근법은 다음과 같습니다.

• priority queue를 이용한다. 낮은 값일수록 우선 순위가 높다.
• 한번 계산 시마다 pq.top의 값을 pop한다. 이를 N-1번 반복하고 나면 그 다음에 pq.top의 값이 원하는 답이 아닐까?

구체적으로는 아래와 같이 시도했습니다.

• 맨 처음 입력받은 소수들을 vector형 container 'primes' 에 담습니다.
• primes 내의 수들을 priority queue형 container 'pq'에 담습니다.
• N-1번 동안, pq.top의 값을 꺼내어 primes의 값들과 각각 곱한 후, 그 결과를 전부 pq.push합니다. 그 다음, 꺼낸 pq.top의 값과 현재 pq.top의 값이 같지 않을 때까지 pq.pop을 해 줍니다.
• pq.push를 할 때, 문제의 제한사항인 2^31보다 값이 크지 않다면 push하지 않습니다. 이는 int형 변수의 크기 제한이기도 합니다.
• 연산이 끝나면, pq.top을 결과로 출력합니다.

메모리 초과에 걸리기 매우 쉬운 문제입니다. 풀 때 조심하세요!

메모리 초과...