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

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

1715번: 카드 정렬하기

난이도: solved.ac 골드 4

 

 

처음에 문제 풀이를 시도했을 때

 

이게 골드 4? 너무 쉬운데? ㅋㅋㅋㅋㅋㅋ 하고 답안을 제출했지만

 

틀렸습니다

 

....?

 

'어디가 틀린 거지?' 하고 의아했던 문제다

 

이 문제에서 주의할 점 두 가지가 있다

 

1. 비교할 카드 묶음의 개수가 남아있는 카드 묶음 중 최소가 되어야 하는 점

 

2. N = 1일 때는 비교할 대상이 없으므로 0이 출력되어야 한다는 점

 

1번의 경우를 예를 들어 설명하겠다

 

10개 짜리로 된 5개의 카드 묶음이 있다고 할 때(10, 10, 10, 10, 10)

 

10 + 10 = 20

20 + 10 = 30

30 + 10 = 40

40 + 10 = 50

으로 20 + 30 + 40 + 50 = 140이 아니라

 

처럼 묶여서

 

10 + 10 = 20

10 + 10 = 20

10 + 20 = 30

20 + 30 = 50

으로 20 + 20 + 30 + 50 = 120이 되어야 한다

 

구현은 우선순위 큐를 이용하였다

 

자료구조에서 배운 우선순위 큐를 복습하기 위해

 

책 '윤성우의 열혈 자료구조'에 나온 코드를 참고하면서 풀었다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define HEAP_LEN 100001
#define TRUE 1
#define FALSE 0

typedef int PriorityComp (int data1, int data2);	// 우선 순위를 정해줄 함수

typedef struct _heap {
	PriorityComp* comp;
	int numOfData;
	int heapArr[HEAP_LEN];
} Heap;

int GetParentIDX(int idx);
int GetLChildIDX(int idx);
int GetRChildIDX(int idx);
int GetHighPriChildIDX(Heap* ph, int idx);
int numPriorityComp(int a, int b);
void PQueueInit(Heap* ph, PriorityComp pc);
int PQIsEmpty(Heap* ph);
void PEnqueue(Heap* ph, int num);
int PDequeue(Heap* ph);

int main() {
	int N;
	Heap pq;
	scanf("%d", &N);

	PQueueInit(&pq, numPriorityComp);

	int num;
	for (int i = 0; i < N; i++) {
		scanf("%d", &num);
		PEnqueue(&pq, num);
	}
	int a, b;
	int total = 0;

	while(!PQIsEmpty(&pq)) {
		a = PDequeue(&pq);
		if (PQIsEmpty(&pq))
			break;
		b = PDequeue(&pq);
		total += a + b;
		PEnqueue(&pq, a + b);
	}
	printf("%d", total);
	return 0;
}


int GetParentIDX(int idx) {
	return idx / 2;
}

int GetLChildIDX(int idx) {
	return idx * 2;
}

int GetRChildIDX(int idx) {
	return idx * 2 + 1;
}

int GetHighPriChildIDX(Heap* ph, int idx) {
	if (GetLChildIDX(idx) > ph->numOfData)	// child가 없을 때
		return 0;
	else if (GetLChildIDX(idx) == ph->numOfData)	// child가 하나 있을 때(child는 왼쪽부터 채워지므로)
		return GetLChildIDX(idx);	// 그 하나 있는 child의 index를 return
	else {		// child가 2개 있을 때
		if (ph->comp(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)]) < 0)
			return GetLChildIDX(idx);	// left child가 right child보다 작을 때
		else
			return GetRChildIDX(idx);	// left child가 right child보다 크거나 같을 때
	}
}

int numPriorityComp(int a, int b) {
	/*
    a가 b보다 크면 양수
    a와 b가 같으면 0
    a가 b보다 작으면 음수 출력
    */
    return a - b;
}

void PQueueInit(Heap* ph, PriorityComp pc) {
	ph->numOfData = 0;
	ph->comp = pc;
}

int PQIsEmpty(Heap* ph) {
	if (ph->numOfData == 0)
		return TRUE;
	else
		return FALSE;
}

void PEnqueue(Heap* ph, int num) {
	int idx = ph->numOfData + 1;
	while (idx != 1) {
		if (ph->comp(num, ph->heapArr[GetParentIDX(idx)]) < 0) {
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else
			break;
	}
	ph->heapArr[idx] = num;
	(ph->numOfData)++;
}

int PDequeue(Heap* ph) {
	int retnum = ph->heapArr[1];
	int lastElem = ph->heapArr[ph->numOfData];

	int parentIdx = 1;
	int childIdx;

	while (childIdx = GetHighPriChildIDX(ph, parentIdx)) {
		if (ph->comp(lastElem, ph->heapArr[childIdx]) <= 0)
			break;
		ph->heapArr[parentIdx] = ph->heapArr[childIdx];
		parentIdx = childIdx;
	}
	ph->heapArr[parentIdx] = lastElem;
	(ph->numOfData)--;
	return retnum;
}