[Jungol] 정올 1190 모두더하기

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

Approach

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

힙(Heap) 자료구조란?

N개의 수가 주어졌을 때 덧셈 연산은 총 N-1번 필요합니다.

더할 때 마다 더하는 두 수를 최소로 해야 하므로 N개의 수들을 계산할 때,

남은 숫자들 중에서 매번 최솟값 2개로해서 더해갑니다.

결국, 매 연산마다 최솟값을 빨리 찾아야 하므로 최소 힙 구조 이용

---

#include <stdio.h>
 
const int LM = 5010;
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;
}