[백준/c++] 20044 - Project Teams

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

20044번: Project Teams

---

1) 풀이

두명씩 팀을 짜되, 각 팀의 코딩 역량이 가능한 적은 차이가 나도록, 즉 각 팀들의 코딩역량이 최대한 밸런스를 이루도록 팀을 짠 후 최소의 코딩역량을 가진 팀의 역량을 출력하는 문제이다.

 

각 팀들의 코딩역량이 밸런스를 이루기 위해서는 가장 큰 값+가장 작은 값 의 순대로 팀을 짜면 된다.

가령 각 학생의 역량을 저장하는 자료구조를 deque(덱)으로 사용했다고 하자.

학생들의 역량을 모두 입력받은 뒤 오름차순으로 정렬하고 덱의 front와 back을 더하여 팀을 짜준 뒤 front와 back을 pop하는 과정을 반복한다. 

이 과정에서 더해준 값 중 가장 최소의 값을 정답으로 출력하면 되는 것이다!

이것만 알면 사실 크게 어려운 점은 없는 문제이다.

 

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
deque<int>d; //코딩역량을 저장해둘 덱
int n;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < 2 * n; i++) {
		int t;
		cin >> t;
		d.push_back(t);
	}
	sort(d.begin(), d.end()); 

	int ans = d.front() + d.back(); //정답으로 출력할 변수. 
	//맨앞과 맨뒤를 더한 값을 기준으로 최소의 값을 찾아 출력.
	d.pop_front();
	d.pop_back();
	while (!d.empty()) {
		ans = min(ans, d.front() + d.back()); //반복문을 통해 제일 작은 값을 알아냄
		d.pop_front();
		d.pop_back();
	}
	cout << ans << '\n';

}

3) 참고자료

- deque 사용법

blockdmask.tistory.com/73