[C++] 백준 20044번 Project Teams

1. 문제이해

20044번: Project Teams (acmicpc.net)

20044번: Project Teams

 

프로젝트 팀 하나는 2명의 학생으로 구성되며, 팀의 개수와 각 학생들의 코딩 역량이 주어진다.

코딩역량이 팀별로 고르게 분포되도록 팀을 구성하려고 할때,

팀의 코딩역량의 최소값을 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

문제를 읽고 이해가 안가서 한참을 들여다 본 문제였다. (결국에는 예제를 보고 이해했다.)

프로젝트 팀을 2명씩 조를 짜 구성하되, 팀의 코딩역량이 최대한 고르게 분포되도록 해야하는 문제이다.

 

위의 예제 1을 보자.팀의 개수(N)가 2로 주어지고, 학생들은 두명이 한 팀(2N)이므로 4명이 된다.

각 학생들의 코딩 역량은 1, 7, 5, 8 이다.이때, 팀을 나누는 경우의 수는 다음과 같다.

 

(1, 8) (7, 5)

(1, 7) (5, 8)

(1, 5) (7, 8)

 

각 팀의 코딩 역량이 첫번째 경우는 9, 12

두번째 경우는 8, 13

세번째 경우는 6, 15

첫번째 경우가 가장 코딩역량이 고르게 분포된다.

(두 팀의 코딩역량의 차이가 가장 작다.)

 

즉, 코딩역량이 가장 고르게 분포되려면,

(가장 코딩역량이 높은 학생, 가장 코딩역량이 낮은 학생),

(2번째로 코딩역량이 높은 학생, 2번째로 코딩역량이 낮은 학생)

.

.

.

순서대로 배치해 나가야 한다.

 

 

 

3.소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int student[10000];	// 학생들의 코딩역량

int main() {
	int N;	// 팀의 개수
	int current = 0;
	int min = 0;

	cin >> N;

	for (int i = 0; i < 2 * N; i++) {
		cin >> student[i];
	}

	// 학생들의 코딩 역량 정렬
	sort(student, student + 2 * N);	

	// min 초깃값 설정
	min = student[0] + student[2 * N - 1];

	for (int i = 0; i < 2 * N; i++) {
    	// 코딩역량이 i번째로 큰 학생, i번째로 작은 학생을 조합
		current = student[i] + student[2 * N - i - 1];
		if (min > current) {	// 최솟값을 찾아나감
			min = current;
		}
	}

	cout << min;

	return 0;
}

팀의 개수(N)와 학생들의 코딩 역량(student[i])을 입력받고,

쉽게 더해주기 위해 학생들의 코딩역량을 정렬했다. (오름차순)

 

min의 초기값을 (코딩역량이 가장 큰 학생) + (코딩 역량이 가장 작은 학생) 으로 설정 후,

for문을 통해 코딩역량이 큰 학생과 작은 학생을 짝지어 더해나갔다.

이후 현재 더한 코딩역량값(current)이 기존의 min(코딩역량 최소값)보다 작다면,

min을 current로 다시 초기화했다.

 

 

---

구현이 크게 어렵지 않은 그리디 알고리즘이었다.

이제 실버3 그리디 알고리즘으로 넘어가야 하나..😱

걱정 반 기대 반이다..

언제까지고 4단계에 머무를 순 없으니, 조만간 실버3으로 올라가야지💪