[Jungol] 정올 1318 못생긴 수

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=597&sca=30

Approach

[그래프] 힙(Heap) 자료구조란? 

힙(Heap) 자료구조란?

1부터 차례대로 못생긴 수인지 확인하는 방법 가능

▶ ugly[i] = i번째 못생긴 수

하지만 아래와 같이 각 수가 (2, 3, 5)로 이루어져 있는지 확인하는 것은 TLE 발생

bool isUgly(int num) {
    int i, mod[3] = { 2, 3, 5 };
    for (i = 0; i < 3; ++i) {
        while (num % mod[i]) {
            num /= mod[i];
        }
    }
    return num == 1;
}

첫 번째 수 1을 기본으로 하여 2, 3, 5가 곱해진 수들만 ugly[]에 저장

배열 heap[] 크기 = 4500 (1500개 이므로 원소가 중복되더라도 1500 * 3을 넘지 않습니다.)

최소 힙 구조 이용

1. 최소힙에 1을 넣는다.

2. 1500개의 못생긴 수가 ugly[]에 저장될 때까지 반복

    - 최소힙에서 수를 꺼낸다.(현재 heap에서 최솟값에 해당) 이를 num이라고 하자

    - num이 이미 나온 수라면 continue

    - num이 처음 나온 수라면 ugly[]에 저장하고

      num에 2, 3, 5를 곱한 값을 heap[]에 넣는다.

 

시뮬레이션

① ugly[] = 1

    heap[] = 2 3 5

② ugly[] = 1 2

    heap[] = 3 5 4 6 10

③ ugly[] = 1 2 3

    heap[] = 4 5 9 6 6 10 15

④ ugly[] = 1 2 3 4

    heap[] = 5 6 8 12 6 10 9 15 20

⑤ ugly[] = 1 2 3 4 5

    heap[] = 6 6 8 10 15 10 9 15 12 20 25

⑥ ugly[] = 1 2 3 4 5 6

    heap[] = 6 10 8 12 12 10 9 15 25 20 15 18 30

⑦ 여기서 heap[]에서 pop() = 6은 이미 ugly 배열에 있으므로 continue됩니다.

    다음과 같이 heap[]에서 원소를 재구성합니다.

    → heap[] = 8 10 9 12 12 10 30 15 25 20 15 18

⑧ ugly[] = 1 2 3 4 5 6 8

    heap[] = 9 10 10 12 12 16 30 15 25 20 15 18 24 40

▶ 3반쩨 못생긴 수 = ugly[3] = 3 (시작 인덱스 = 1)

▶ 7반쩨 못생긴 수 = ugly[7] = 8 (시작 인덱스 = 1)

---

1500번째 수는 859,963,392 따라서 typedef long long LL; 이용

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 1500;
typedef long long LL;
LL ugly[LM + 4], heap[LM * 3 + 10], num;
int heapSize, nth;
inline void swap(LL &a, LL &b) {
    LL t = a; a = b; b = t;
}
 
void push(LL num) {
    heap[++heapSize] = num;
    int child = heapSize;
    while (child > 1 && heap[child] < heap[child / 2]) {
        swap(heap[child], heap[child / 2]);
        child /= 2;
    }
}
 
int pop() {
    int parent = 1, child = 2, val = heap[1];
    swap(heap[1], heap[heapSize--]);
 
    while (child <= heapSize) {
        if (child < heapSize && heap[child + 1] < heap[child]) child++;
        if (heap[child] >= heap[parent]) break;
        swap(heap[child], heap[parent]);
        parent = child, child *= 2;
    }
    return val;
}
 
void getUglyNumber() {
    push(1);
    for (int idx = 0; idx < LM; ) {
        num = pop();
        if (num == ugly[idx])
            continue;
             
        ugly[++idx] = num;
        push(num * 2);
        push(num * 3);
        push(num * 5);
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    // Test Case를 입력 받는 문제이므로 매번 못생긴 수인 확인하지 않고
    // 미리 구하여 ugly[]에 저장
    getUglyNumber();
     
    // scanf()가 오류나지 않는 가정하에 입력받은 숫자가 0인 경우 종료
    while (scanf("%d", &nth) && nth) {
        printf("%lld\n", ugly[nth]);
    }
    return 0;
}