BOJ 1715 : 카드 정렬하기

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/1715

 

 

카드 비교 횟수를 줄이기 위해서는 가장 작은 수의 두 카드를 비교해야한다.

그리고 카드를 합친다. (+ 횟수를 누적한다.)

그러면 다시 남은 카드(+ 합친카드 포함) 중에서 가장 작은 수의 두 카드를 비교해야한다.

 

따라서, 우선순위 큐를 이용한다.

가장 작은 두 카드는 두 번 pop하면 얻을 수 있고,

합친 카드를 우선순위 큐에 넣어도 우선순위 큐를 두 번 pop하면 가장 작은 두 카드를 구할 수 있다.

#include <stdio.h>

int N;

int heap[100100];
int hn;

int pop(int* heap, int& hn)
{
	int tmp, ret;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--] = 0x7fff0000;

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i] < heap[i * 2] && heap[i] < heap[i * 2 + 1]) break;
		else if (heap[i * 2] < heap[i * 2 + 1])
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(int* heap, int& hn, int x)
{
	int tmp;

	heap[++hn] = x;
	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2] <= heap[i]) break;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

int main()
{
	int total, sum;

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		int tmp;
		scanf("%d", &tmp);

		push(heap, hn, tmp); /* 카드를 모두 넣는다. */
	}

	total = sum = 0;
	for (int i = 0; i < N - 1;i++)
	{
		sum = 0;
		sum += pop(heap, hn); /* 가장 작은 카드 2개를 뽑는다. */
		sum += pop(heap, hn); 

		total += sum; /* 횟수를 누적한다. */
		push(heap, hn, sum); /* 합친 카드를 다시 heap에 넣는다. */
	}

	printf("%d\n", total);

	return 0;
}