1 Problem B : 못생긴 수

소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기

수열로 늘어 놓으면 1, 2, 3, 4, 5, ,6, 8, 9, 10, 12, ...

정수 n이 주어졌을 때, n번째 못생긴 수를 출력하는 프로그램을 작성하시오

 

- heap을 만들어서 ugly[cnt] 에 못생긴 수를 저장

- 처음 부터 *2, *3, *5 를 해가며 3개의 숫자를 push

- minheap을 사용하여, 가장 작은 수를 pop

- 위의 내용 MAXN까지 반복

 

#include <stdio.h>
typedef long long LL;

LL heap[5000] = { 0, 1 }, ugly[1600], hcnt = 1; // 첫 힙에 0과 1을 넣어둠

void Swap(int x, int y) { LL z = heap[x]; heap[x] = heap[y]; heap[y] = z; }

void push(int p) // p는 힙의 인덱스
{
	if (p <= 1 || heap[p / 2] <= heap[p]) return; // 0보다 작거나, 부모가 더 작거나 같으면 변경 안함
	Swap(p / 2, p); // 변경
	push(p / 2); // 자리를 찾아감
}

void pop(int p)
{
	int np = p * 2; // 자식과 비교
	if (np > hcnt) return; // 자식이 없으면
	if (np < hcnt && heap[np] > heap[np + 1]) np++; // 자식이 있고, 왼쪽 자식이 더 크면, 작은 것을 가지고 놀아야 하므로++
	if (heap[p] <= heap[np]) return; // 변경하지 않아도 되면 return
	Swap(p, np); // 변경
	pop(np); // 재귀로
}

int main()
{
	int n, cnt = 1;
	while (cnt <= 1500) {
		ugly[cnt] = heap[1]; // ugly 첫 번째 요소는 1
		heap[1] = heap[hcnt--]; // 젤 마지막 인덱스 것을 젤 위로 올리고
		pop(1);
		if (ugly[cnt] == ugly[cnt - 1]) // 동등한 것이 들어올 경우
			continue;
		heap[++hcnt] = ugly[cnt] * 2; push(hcnt); // 2,3,5 를 곱하면 ugly 숫자가 나옴
		heap[++hcnt] = ugly[cnt] * 3; push(hcnt);
		heap[++hcnt] = ugly[cnt] * 5; push(hcnt);
		cnt++;
	}
	while (1) {
		scanf("%d", &n);
		if (n == 0) break;
		printf("%lld\n", ugly[n]);
	}
	return 0;
}

1 2 9 0

1 2 10