4. 11066 파일 합치기 [힙]

원본 출처 : https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

문제 풀이 :

//힙을 이용해서 풀어보기.
//파일 합치기 알고리즘과 같은 알고리즘
//DP 풀이 해설 : https://js1jj2sk3.tistory.com/3
#include <stdio.h>
#define MAX_HEAP    (50002)
#define SWAP(a,b) {int t; t=a; a=b; b=t;}
int N;
int heap[MAX_HEAP + 1];
int lastnode = 0;
int Heap_Push(int d)
{
	int p, c, temp; //p:parents c:children
	if (lastnode == MAX_HEAP) return 0;
	lastnode++;
	heap[lastnode] = d; //마지막에 넣고 탐색
	c = lastnode;       //시작은 마지막이 자식이됨
	p = c / 2;          //자식의 절반은 부모
	while (p > 0) {      //부모노드가 최상위 노드까지 반복
		if (heap[p] > heap[c]) {
			//자식이 더 큰가? -> swap
			temp = heap[p]; heap[p] = heap[c]; heap[c] = temp;

			c = p;
			p = c / 2;  //부모 타고 올라가기
		}
		else break;     //비교 대상이 더 크지 않으면 break;
	}
	return 0;
}
int Heap_Pop(int* d)
{
	int p, l, r, c, temp;       //p:parents l:left r:right c:children
	if (lastnode == 0)return 0; //Empty;
	*d = heap[1];               //맨 처음 꺼 pop
	//pop한 뒤 힙트리를 유지하는 안정화 작업 필요
	heap[1] = heap[lastnode];   //마지막 노드를 맨 앞으로
	lastnode--;                 //lastnode 한칸 땡기기
	p = 1; l = p * 2; r = l + 1;//push와 반대로 자식 타고 내려가기
	while (l <= lastnode) {
		//마지막 노드가 왼쪽 노드보다 크거나 같음
		if (l == lastnode) c = l;           //자식이 하나 뿐이라 고민 할 필요 없음.
		else if (heap[l] < heap[r])c = l;    //자식이 둘 있을 때 둘 중 큰 값으로 내려간다.왼쪽 자식 고를지 오른쪽 자식 고를지 비교(내려간다 = 나와 교환)
		else c = r;
		if (heap[p] > heap[c]) {
			temp = heap[p]; heap[p] = heap[c]; heap[c] = temp;
			p = c;
			l = p * 2;
			r = l + 1;
		}
		else break;
	}
	return 1;
}
int a[MAX_HEAP];
int mtemp[MAX_HEAP];
void quick_sort(int s, int e) {
	int L, T, P = e, temp;
	if (s >= e) return;  //종료 조건
	for (L = s, T = s; L < e; L++) {
		if (a[L] < a[P]) {
			if (L != T) { temp = a[L]; a[L] = a[T]; a[T] = temp; }
			T++;
		}
	}
	if (P != T) { temp = a[P]; a[P] = a[T]; a[T] = temp; }
	quick_sort(s, T - 1);
	quick_sort(T + 1, e);
}

int main(void) {
	int i, j, k, num, d1 = 0, d2 = 0, sol = 0, sum = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &num);
		Heap_Push(num);
	}
	//Heap 트리를 이용하여 풀기
	for (k = 0; k < N - 1; k++) {//시작위치.
		Heap_Pop(&d1);
		Heap_Pop(&d2);
		sol += (sum = d1 + d2);
		Heap_Push(sum);
	}
	printf("%d\n", sol);
}

예를 들어 C1, C2, C3, C4가 있을 때 최솟값이 나오기 위해서는 가장 작은 값1 + 가장 작은 다음 값2 가 먼저 연산이 되어야 한다. 그리고 이 연산 결과가 다시 힙트리에 들어가면 된다. 이를 반복