[백준] 1715번 문제풀이

문제 : www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

알고리즘 :

1. 입력을 받은 뒤 priority heap(우선순위 힙) 에 push함.

2. pop을 하면 최솟값이 나옴. pop을 2번 하고, 이걸 더한걸 Sum에 더함.

3. pop 2번한걸 push함.

4. 이 과정을 반복함 (n-1번)

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_SIZE 100001

int heap[MAX_SIZE];
int heapSize = 0;

void heapInit(void)
{
	heapSize = 0;
}

int heapPush(int value)
{
	if (heapSize + 1 > MAX_SIZE)
	{
		printf("queue is full!");
		return 0;
	}

	heap[heapSize] = value;

	int current = heapSize;
	while (current > 0 && heap[current] < heap[(current - 1) / 2])
	{
		int temp = heap[(current - 1) / 2];
		heap[(current - 1) / 2] = heap[current];
		heap[current] = temp;
		current = (current - 1) / 2;
	}

	heapSize = heapSize + 1;

	return 1;
}

int heapPop(int* value)
{
	if (heapSize <= 0)
	{
		return -1;
	}

	*value = heap[0];
	heapSize = heapSize - 1;

	heap[0] = heap[heapSize];

	int current = 0;
	while (current * 2 + 1 < heapSize)
	{
		int child;
		if (current * 2 + 2 == heapSize)
		{
			child = current * 2 + 1;
		}
		else
		{
			child = heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
		}

		if (heap[current] < heap[child])
		{
			break;
		}

		int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		current = child;
	}
	return 1;
}

int main(int argc, char* argv[])
{
	heapInit();

	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int value;
		scanf(" %d", &value);
		heapPush(value);
	}

	long long int sum = 0;
	n--;
	while (n--)
	{
		int value1;
		if (heapPop(&value1) == -1) { break; }
		sum += (long long int)value1;

		int value2;
		heapPop(&value2);
		sum += (long long int)value2;

		heapPush(value1 + value2);
	}
	printf("%lld\n", sum);

	return 0;
}

하지만 나는 기존에, 이러한 알고리즘으로 접근하였다.

1. sort(오름차순)

2. sum1으로 앞, 뒤 index를 더함.

3. sum2으로 sum1을 더함.

이렇게 접근했는데, 완전히 잘못된 접근이었다. 반성을 많이 하고 있다.

TestCase만 보고 성급하게 접근을 하였다. 다음부터는 문제를 꼭 다 읽고, 분석해 볼 것이다.

그래도 잘한 점은, 구글링을 하였지만 끝까지 포기하지 않았다는 점이다.

사실 굉장히 스트레스를 받았었다. 잘못된 게 없는 줄 알고.

이 문제는 Sort 방식으로는 풀 수 없다. 풀더라도, 시간이 많이 걸릴 것이다.

내가 풀었던 방법이다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_ARR 100001

void merge(int* arr, int left, int mid, int right);
void mergeSort(int* arr, int left, int right);

int temp[MAX_ARR];

int main(void)
{
	int n;
	int arr[MAX_ARR];
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf(" %d", &arr[i]);
	}

	mergeSort(arr, 0, n - 1);

	long long int sum;
	sum = 0;

	arr[n] = 0;
	for (int i = 0; i < n; i+=2)
	{
		sum += (long long int)arr[i] + (long long int)arr[i + 1];
	}

	if (n == 1) { printf("0\n"); }
	else { printf("%lld\n", sum); }


	return 0;
}

void mergeSort(int* arr, int left, int right)
{
	if (left == right) { return; }
	int mid = (left + right) / 2;
	mergeSort(arr, left, mid);
	mergeSort(arr, mid + 1, right);
	merge(arr, left, mid, right);
	return;
}

void merge(int* arr, int left, int mid, int right)
{
	int i = left;
	int j = mid + 1;
	int k = left;

	while (i <= mid && j <= right)
	{
		if (arr[i] < arr[j])
		{
			temp[k++] = arr[i++];
		}
		else
		{
			temp[k++] = arr[j++];
		}
	}
	while (i <= mid) { temp[k++] = arr[i++]; }
	while (j <= right) { temp[k++] = arr[j++]; }
	for (int a = left; a <= right; a++)
	{
		arr[a] = temp[a];
	}
	return; 
}

참고로 priority heap 소스코드는 다른 곳에서 가지고 왔다.

테스트 케이스:

걸린 시간 : 139분(알고리즘 : 5분, 코딩 및 디버깅 : 134분)

알고리즘에 신경 쓴 시간을 보니까... 참으로 안타깝다.

안 풀릴 땐 코드가 잘 되었는지 보고, TestCase를 만들어서 확인해보고, 그래도 안 되면 다시 알고리즘을 정독해야 할 것 같다.

'프로그래밍 > 개발 이야기' 카테고리의 다른 글

[백준] 5585번 문제풀이 (2)	2021.04.09
[백준] 12904번 문제풀이 (0)	2021.04.09
[백준] 10162번 문제풀이 (0)	2021.04.07
[백준] 1946번 문제풀이 (0)	2021.04.07
[백준] 2217번 문제풀이 (2)	2021.04.07

[백준] 1715번 문제풀이

'프로그래밍 > 개발 이야기' 카테고리의 다른 글

댓글

티스토리툴바

[백준] 1715번 문제풀이

'프로그래밍 > 개발 이야기' 카테고리의 다른 글

관련글

댓글

티스토리툴바