[백준/BOJ] 20044. Project Teams [Silver 4]

20044. Project Teams

문제출처 : https://www.acmicpc.net/problem/20044

일단 문제에 기호가 많아서 이해하기 어려울수도 있는데, 간단히 말하면
한팀에 2명씩 조를 짜는데,
첫번째 입력에 조의 갯수를 입력받는다. (실제사람수는 2n이 될것이다.)
그리고 팀원 코딩역량의 합을 최대한 일정하게 유지하려고 한다는것은, 최대한 차이가 안나게 밸런스를 맞추겠다는 뜻이다. 즉, 가장 못하는사람+가장 잘하는사람 그다음 못하는사람 + 그다음 잘하는사람 이런식으로 조를짠다는 뜻이고,
작성할 프로그램 목적은 Sm = min{w(Gi) | 1 ≤ i ≤ n}이 최대화되도록 n개의 팀 G1, G2, …, Gn 을 구성하고 이때 Sm을 출력하는 것이다. 의미를 간단하게 나타내면 가장못하는 팀의 역량값을 최대화시켜 출력하라는 의미이다.

code

#include <stdio.h>
void QuickSort(int *arr,int start,int end)
{
	if (start >= end)
		return;
	int piv = start, left = start + 1, right = end, temp;
	while (left <= right)
	{
		while (left <= end && arr[left] <= arr[piv])
			left++;
		while (right > start && arr[right] >= arr[piv])
			right--;
		if (left > right)
		{
			temp = arr[right];
			arr[right] = arr[piv];
			arr[piv] = temp;
		}
		else
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
	}
	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
int main()
{
	int n, N, i, arr[10000] = { 0 }, sum = 0, min=200000;
	scanf("%d", &n);
	N = 2 * n;
	for (i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	QuickSort(arr, 0, N - 1);

	for (i = 0; i < N; i++)
	{
		sum = arr[i] + arr[N - 1 - i];
		if (sum < min)
			min = sum;
	}
	printf("%d", min);
	return 0;
}

그래서 코드를 보면 소트를 해서(오름차순이던 내림차순이던) 처음과 끝에서부터 한사람씩 조를 맺고, 각 팀을 비교해서최솟값을 구한다. (초기 최솟값은 200000으로 설정했는데, 이는 학생들의 코딩역량최댓값이 100000이고, 사람마다 역량은 다르기때문에 팀의 역량최댓값은 199999가 된다.)

알고리즘 자체는 굉장히 쉬운편이다. 퀵소트를 하면서 느끼는거지만 맨날 할때마다 헷갈린다 ㅠㅠ