백준(baekjoon) [C] - 1715번: 카드 정렬하기

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

---

#include <stdio.h>  // 카드 정렬하기
#include <stdlib.h>

typedef struct
{
	int data;
}node;

typedef struct
{
	node arr[100001];
	int size;
}HEAP;

void push(HEAP* h, int num)
{
	int i;
	i = ++(h->size);

	while ((i != 1) && num < h->arr[i / 2].data)
	{
		h->arr[i].data = h->arr[i / 2].data;
		i /= 2;
	}
	h->arr[i].data = num;
}

int pop(HEAP* h)
{
	int root, temp;
	root = h->arr[1].data;
	temp = h->arr[(h->size)--].data;

	int parent = 1;
	int child = 2;

	while (child <= h->size)
	{
		if ((child < h->size) && (h->arr[child].data > h->arr[child + 1].data))
		{
			child++;
		}

		if (temp <= h->arr[child].data)
			break;

		h->arr[parent].data = h->arr[child].data;
		parent = child;
		child *= 2;
	}
	h->arr[parent].data = temp;

	return root;
}


int main()
{
	int n;
	scanf("%d", &n);

	HEAP h;
	h.size = 0;

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

	long long int sum = 0;
	while (h.size > 1)
	{
		int a, b;
		a = pop(&h);
		b = pop(&h);
		sum += (a + b);
		push(&h, a + b);
	}
	printf("%lld", sum);


	return 0;
}

---

MEMO

-- 최소 힙을 구현하면 될 것 같은 아이디어가 떠올랐지만 더하는 부분들을 어떻게 처리해야할지 몰라서 결국 구글링

-- 일단 입력값들을 push하고 main 함수의 while 문에서 가장 작은 두값(a, b)를 더한 값을 다시 push하는 것으로 해결

-- sum --> long long int --> 최대 1000의 숫자가 100000개 가량 들어올 수 있기 때문에

 

!! 차분하게 생각해보기 !!