못생긴 수

못생긴 수

 

제한시간: 1000 ms    메모리제한: 32 MB

 

못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 하며, 이를 수열로 늘어놓으면 다음과 같다.

 

1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

 

이는 처음나오는 10개의 못생긴 수이며, 편의상 1을 포함하도록 하자. 정수 n이 주어졌을 때, n번째 못생긴 수를 출력하는 프로그램을 작성하라.

 

한 줄에 양의 정수 n(n≤1,500)이 주어진다. 입력에 0 이 주어질 때까지 계속 한다.

 

출력에는 n번째 못생긴 수를 출력한다.

 

1

2

9

0

 

1

2

10

 

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

LL heap[5000] = { 0, 1 }, ugly[1600], hcnt = 1; // 1500 * 3 = 4500, 1500 2개의 제약 조건 있음

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

void push(int p)
{
	if (p <= 1 || heap[p / 2] <= heap[p]) return;
	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;
	Swap(p, np);
	pop(np);
}

int main()
{
	freopen("input.txt", "r", stdin);
	int n, cnt = 1;
	while (cnt <= 1500) {
		ugly[cnt] = heap[1]; // 아래 3개 연산 이후에 가장 작은 값을 넣음
		heap[1] = heap[hcnt--];
		pop(1);
		if (ugly[cnt] == ugly[cnt - 1]) continue; // 같은 숫자이면 넘어감
		heap[++hcnt] = ugly[cnt] * 2; 
		push(hcnt);
		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;
}