11. 1318 : 못생긴 수

원본 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=597&sca=50&sfl=wr_subject&stx=%EB%AA%BB%EC%83%9D%EA%B8%B4&sop=and

JUNGOL | 못생긴 수 > 문제은행

문제 풀이 : 

#include <stdio.h>
#define MAX 1500
#define SWAP(a,b) {long long t;t=b;b=a;a=t;}
long long heap[MAX * 3 + 1];    //3배 공간 필요.(2,3,5를 곱하기 때문)
long long list[MAX + 50];
int last_p = 0;
int push(long long d) {
	int p_p, c_p;
	//FULL check
	if (last_p == MAX * 3 + 1) return 0;
	heap[++last_p] = d; //일단 맨 뒷 노드에 입력받은 숫자를 넣음.
	c_p = last_p;
	p_p = c_p / 2;
	while (p_p > 0) {
		if (heap[c_p] < heap[p_p]) { //자식이 부모보다 작으면 SWAP : 최소 힙트리
			//SWAP 하기
			SWAP(heap[c_p], heap[p_p]);
			//부모타고 올라가기
			c_p = p_p;
			p_p = c_p / 2;
		}
		else break;
	}
}
int pop(long long* d) {
	int p_p, c_p, l_c_p, r_c_p; //왼쪽 오른쪽 자식 방향 포인터 추가
	//Empty check
	if (last_p == 0) return 0;
	*d = heap[1];   //heap의 루트노드를 PoP!
	//맨 마지막 노드를 루트 노드에 옮김
	//SWAP(heap[last_p--], heap[1]);
	heap[1] = heap[last_p--];

	//이번엔 자식 타고 내려가기
	p_p = 1;    //일단 루트노들르 부모로 잡고 왼쪽,오른쪽 자식 index 설정
	l_c_p = p_p * 2;
	r_c_p = l_c_p + 1;

	//자식 노드가 없을 때 까지 타고 내려가기
	while (l_c_p <= last_p) {//왼쪽 자식이 더이상 없을 때 까지(자식은 왼쪽부터 생성되기 때문)
		if (l_c_p == last_p) {
			//자식이 하나뿐이면 바로 왼쪽 자식 인덱스 설정
			c_p = l_c_p;
		}
		else {
			//자식이 둘이면 더 작은 자식 찾기 (최소 heap)
			c_p = (heap[l_c_p] < heap[r_c_p]) ? (l_c_p) : (r_c_p);
		}
		//찾은 자식과 부모 비교
		if (heap[c_p] < heap[p_p]) {
			//자식이 더 작으면 부모와 SWAP : 최소 heap
			SWAP(heap[c_p], heap[p_p]);
			//자식 타고 내려가기
			p_p = c_p;
			l_c_p = p_p * 2;
			r_c_p = l_c_p + 1;
		}
		else break;
	}

}
void solve(void) {
	//리스트에 못생긴 수 1500개 담기
	int cnt = 1;
	long long prev = 0, data;
	push(1);                    //1부터 시작
	while (cnt <= 1500) {        //1500개 담을 동안 반복
		pop(&data);
		if (prev == data) continue; //같은 수는 스킵
		prev = data;
		list[cnt] = data;
		cnt++;
		push(data * 2);
		push(data * 3);
		push(data * 5);
	}
}
int main(void) {
	int i, n;
	solve();
	for (;;) {
		scanf("%d", &n);
		if (n == 0) break;
		printf("%lld\n", list[n]);
	}
	return 0;
}

 

가장 먼저 1를 힙트리에 넣는다. 그 다음 팝 한 값에 2,3,5를 곱해서 다시 힙트리에 넣는데 이 때 중복 되는 수를 제거 해줘야 한다. 조건을 만족하는 팝 값들은 다른 배열에 따로 저장해준다. 이 때 곱해지는 수가 상당히 커지기 때문에 long long 타입을 선언해 주어야 한다.