[Advanced][정올] 1318번 : 못생긴 수

정올 1318 : 못생긴 수

JUNGOL

 

 

 

[풀이 후기]
난이도 : ★★☆☆ (Advanced)
문제 종류 : Sort
해결 방법 : Heap Sort

 

 

* 난이도 구분
★☆☆☆ (Beginner) : 알고리즘 적용만으로 해결 가능
★★☆☆ (Advanced) : 알고리즘을 활용하여 구현해야 해결 가능
★★★☆ (Pro) : 알고리즘을 활용한 구현 + 최적화 아이디어로 해결 가능
★★★★ (Expert) : Pro보다 발전된 최적화 아이디어로 해결 가능

 

---

 

문제

 

 

문제 분석

1. 못생긴 수란, 소인수분해 시, 2, 3, 5 뿐인 수를 말한다. 즉, 이 3가지 수를 곱해서 만들어진 수 이다. 
2. N <= 1500 이므로, 최대 1500번째 못생긴 수를 구해야한다. 
3. 못생긴 수를 작은 순서로 어떻게 빠르게 만들 수 있을지 고민해보자. 

 

---

 

접근 방법

이 문제에서의 핵심은 "못생긴 수를 어떻게 구할 수 있을까?" 이다. 

 

소인수분해를 했을 때, 2, 3, 5 뿐이라는 것이 문제에서 주어졌으므로, 

일단 당연히 2, 3, 5는 못생긴 수 이다. 

 

추가로 2, 3, 5 각각에 2, 3, 5를 곱해도 못생긴 수가 된다. 

2 * 2 = 4
2 * 3 = 6
2 * 5 = 10

3 * 2 = 6
3 * 3 = 9
3 * 5 = 15

5 * 2 = 10
5 * 3 = 15
5 * 5 = 25

 

그러면 이제 이런 방식으로, 2, 3, 5를 곱해서 나온 수에 계속 2, 3, 5를 곱해서 1500개의 수를 구하면 되는 것인가?

그렇지 않다. 

 

 

왜냐하면, 중복을 없애야하고, 오름차순으로 정렬되어야하기 때문이다. 

 

 

따라서, 아래와 같이 Heap을 이용하여 해결할 수 있다. 

1. Min Heap에서 1번 pop 한다. 
2. 이 수를 배열에 저장한다. ( 배열에 i번째 저장하는 수가 i번째 못생긴 수 )
3. 만약에 pop으로 나온 수가, 배열의 마지막 수와 동일하다면, 1번 단계로 돌아간다. 
4. pop으로 나온 수에 2, 3, 5를 곱해서 Heap에 push 한다. 
5. 반복

여기서 배열에 저장하는 수가 바로 못생긴 수 이다. 

그림으로 과정을 확인해보자. 

 

 

 

* Heap Sort에 관한 내용은 아래 포스팅을 참고하자. 

[자료구조][정렬][C/C++] Heap Sort (우선순위 큐)

[자료구조][정렬][C/C++] Heap Sort (우선순위 큐)

 

 

 

 

1. 아래와 같이 초기 세팅을 해두자 

배열 A는 못생긴 수를 저장한다. A[ i ] 는 i번째 못생긴 수를 의미한다. 

Heap에는 1이 push 되어 있다. 

 

 

2. Heap에서 1번 pop을 한다. 

Heap은 Empty 상태가 되고, A[ 1 ] = 1 이 저장된다.  

 

 

3. pop으로 나온 수(=1) 에 2, 3, 5를 곱해서 Heap에 push 한다. 

 

 

4. 자, 이제 다시 Heap에서 1번 pop을 한다. 

A[ 2 ] = 2 가 저장되고, Heap에는 3, 5가 남게 된다. 

 

 

 

5. pop으로 나온 수(=2) 에 2, 3, 5를 곱해서 Heap에 push 한다. 

 

 

6. 반복한다. 

이제, 못생긴 수를 오름차순으로 정렬하고, 중복도 제거하면서 구할 수 있게되었다. 

 

 

---

 

코드

먼저 못생긴 수를 생성하는 부분을 살펴보자. 

 

위 접근방법에서 설명된 1~5 과정을 포함하고 있다. 

void makeNumber() {
	int cnt = 0;

	while (heapSize > 0 && cnt <= 1500) {
		LL num = pop();
		if (A[cnt] == num) continue;

		A[++cnt] = num;
		push(num * 2);
		push(num * 3);
		push(num * 5);
	}
}

 

 

Heap과 Main을 포함한 전체 코드를 살펴보자. 

#include <stdio.h>

using LL = long long;
const int LM = 5000;

LL A[LM];
LL heap[LM];
int heapSize;

inline void swap(LL& a, LL& b) { LL t = a; a = b; b = t; }

void push(LL newData) {
	int c = ++heapSize;
	for (; c >= 1 && newData < heap[c >> 1]; c >>= 1)
		heap[c] = heap[c >> 1];

	heap[c] = newData;
}

LL pop() {
	LL ret = heap[1];
	swap(heap[1], heap[heapSize--]);

	for (int c = 2; c <= heapSize; c <<= 1) {
		if (c < heapSize && heap[c] > heap[c + 1])
			c++;

		if (heap[c] < heap[c >> 1])
			swap(heap[c], heap[c >> 1]);
		else
			break;
	}
	return ret;
}

void makeNumber() {
	int cnt = 0;

	while (heapSize > 0 && cnt <= 1500) {
		LL num = pop();
		if (A[cnt] == num) continue;

		A[++cnt] = num;
		push(num * 2);
		push(num * 3);
		push(num * 5);
	}
}

int main() {
	push(1);	// 초기 setting
	makeNumber();	// 못생긴 수 만들기

	int N;
	while (1) {
		scanf("%d", &N);
		if (N == 0)	break;	// exit
		printf("%lld\n", A[N]);	// N번째 못생긴 수 출력
	}
	return 0;
}

---

 

제출결과

정올 제출 결과