Boj1715_카드정렬하기

Published: December 04, 2018 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

백준 1715 카드정렬하기

• n*n 그리드에 수 2

#include<iostream>
using namespace std;

int h[100000],nowsize=1;
void swap(int &n1, int &n2) {
	int nownode = n1;
	n1 = n2;
	n2 = nownode;
}

void push(int num) {
	h[nowsize] = num;
	int nowidx = nowsize;
	while (nowidx > 1 && h[nowidx]<h[nowidx/2]) {
		swap(h[nowidx], h[nowidx / 2]);
		nowidx /=2;
	}
	nowsize++;
}

int pop() {
	nowsize--;
	int min_num = h[1];
	swap(h[1], h[nowsize]);
	h[nowsize] = 0;
	int nowidx = 1;
	while (nowidx <= nowsize-1) {
		int nextidx;
		if (nowidx * 2 == nowsize - 1) {//한곳만
			nextidx = nowidx * 2;
		}
		else if (nowidx * 2+1 <= nowsize - 1) {//둘다 갈 수 있음.
			nextidx = h[nowidx * 2] < h[nowidx * 2 + 1] ? nowidx * 2  : nowidx * 2+1;
		}
		else break;
		if (h[nextidx] < h[nowidx]) {
			swap(h[nextidx], h[nowidx]);
			nowidx = nextidx;
		}
		else break;
	}

	return min_num;
}

int main() {
	int n,num;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &num);
		push(num);
	}

	if (n == 1) {
		printf("0");
		return 0;
	}

	int ans = 0;
	
	while (nowsize != 1) {
		int temp =  (pop()+pop());
		ans += temp;
		if(nowsize!=1) push(temp);
	}

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

}