[Jungol] 정올 1929 책꽂이 만들기

출처: http://kcwjwbw.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1202&sca=3080

Approach

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

힙(Heap) 자료구조란?

21 = 13 + 8 → 비용 21 발생

13 = 8 + 5 → 비용 13 발생

▶ 총 비용 = 21 + 13 = 34

 

15 = 6 + 0 → 비용 15 발생

6 = 3 + 3 → 비용 6 발생

9 = 4 + 5 → 비용 9 발생

3 = 1 + 2 → 비용 3 발생

▶ 총 비용 = 15 + 6 + 9 + 3 = 33

 

문제 개요는 큰 널빤지 1개를 N개로 자르는 것이지만,

Input Data로 입력받은 원소를 모두 더할 때, 최소 비용으로 더해질 수 있도록 해주는 문제입니다.

ex) Input Data = [8, 5,  8]

① 8 + 8 = 16

    16 + 5 = 21

    ▶ 총 비용 = 16 + 21 = 37

② 5 + 8 = 13

    8 + 13 = 21

    ▶ 총 비용 = 13 + 21 = 34

즉, N개의 원소를 두 개의 수끼리 N-1번 더해서 결과를 구할 때, 두 개의 수가 배열에서 가장 작은 2개의 값입니다.

최소값 2개를 빠르게 찾기 위해 최소 힙 이용.

 

※ [Jungol] 1190 모두 더하기 참고

[Jungol] 정올 1190 모두더하기

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 20010;
int N, heap[LM], heapSize;
long long ans;
inline void swap(int& a, int& b) { int t = a; a = b; b = t; }
 
void push_heap(int num) {
    heap[++heapSize] = num;
    int child = heapSize;
    for (; child > 1 && heap[child] < heap[child / 2]; child /= 2) {
        swap(heap[child], heap[child / 2]);
    }
}
 
int pop_heap() {
    int parent = 1, child = 2, ret = heap[1];
    swap(heap[1], heap[heapSize--]);
    while (child <= heapSize) {
        if (child < heapSize && heap[child + 1] < heap[child]) child++;
        if (heap[parent] <= heap[child]) break;
        swap(heap[parent], heap[child]);
        parent = child, child *= 2;
    }
    return ret;
}
 
void input() {
    scanf("%d", &N);
    int i, val;
    for (i = 0; i < N; ++i) {
        scanf("%d", &val);
        push_heap(val);
    }
}
 
void process() {
    // N-1번 더합니다.
    for (int i = 1; i < N; ++i) {
        int sum = pop_heap() + pop_heap();
        ans += sum;
        push_heap(sum);
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    process();
    printf("%lld", ans);
    return 0;
}