못생긴 수

못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 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

 

min_heap 배열에 1부터 넣고, root를 빼서 ans 배열에 넣음과 동시에 root * 2, root * 3, root * 5를 집어 넣는다.
그리고 그 다음에 2가 root가 되면 2를 2, 3, 5 를 곱해서 heap에 집어 넣고 2는 ans 배열에 넣는다.
한가지 더 짚어야 하는 것은, 만약 지금 root 로 뽑아 내는 것과 바로 직전에 ans 배열에 넣은 것과 같으면
pass한다.

 

 

#include <stdio.h>

typedef long long LL;

 

LL heap[5000];

LL ans[1510];

int n, cnt;

 

void SWAP(LL &x, LL &y) { LL z = x; x = y; y = z; }

 

void push(int p)

{

    if (p <= 1 || heap[p / 2] <= heap[p]) return;

    SWAP(heap[p], heap[p / 2]);

    push(p / 2);

}

 

void pop(int p)

{

    int child = p * 2;

    if (child > n) return;

    if (child < n && heap[child] > heap[child + 1]) child++;

    if (heap[p] <= heap[child]) return;

    SWAP(heap[p], heap[child]);

    pop(child);

}

 

int main()

{

    LL k, num;

    heap[++n] = 1;

    while (cnt <= 1500) {

        k = heap[1];

        heap[1] = heap[n--];

        pop(1);

        if (k == ans[cnt]) continue;

        ans[++cnt] = k;

        heap[++n] = k * 2; push(n);

        heap[++n] = k * 3; push(n);

        heap[++n] = k * 5; push(n);

    }

    while (1) {

        scanf("%lld", &num);

        if (num == 0) break;

        printf("%lld\n", ans[num]);

    }

    return 0;

}

 

 

min_heap 배열에 1부터 넣고, root를 빼서 ans 배열에 넣음과 동시에 root * 2, root * 3, root * 5를 집어 넣는다.

그리고 그 다음에 2가 root가 되면 2를 2, 3, 5 를 곱해서 heap에 집어 넣고 2는 ans 배열에 넣는다.

한가지 더 짚어야 하는 것은, 만약 지금 root 로 뽑아 내는 것과 바로 직전에 ans 배열에 넣은 것과 같으면

pass한다.