문제 출처

1. 문제설명

• 학생들의 코딩 역량이 주어진다.
• 2명의 팀으로 구성할 수 있으며,
  • {1, 7, 5, 8} 이라면 {8, 1}, {7, 5}가 최대가 되는 값이다.
  • 이 중 최소 코딩 역량은 9이므로 9를 출력하면 된다.

2. 알고리즘 설계

• 입력 데이터를 오름차순으로 정렬
• 정렬된 데이터의 양 끝 값(front, back)을 이용해 더한다.
• 양 끝 값을 pop한다.
• 더해진 값을 임시 배열에 저장 한다.

3. 로직

• deque를 사용하면 매우 쉽게 구현 가능
• 오름차순 된 값의 front, back을 더한다.
• 이를 임시 벡터에 넣는다.
• 상기 과정을 모든 데이터에 대해 반복 후, 임시 벡터를 오름차순 정렬
• 임시 벡터의 0번째 index의 값 출력

4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) 
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n; cin >> n;
	deque<int> dq;
	for (int tmp, i = 0; i < n*2; i++) {
		cin >> tmp;
		dq.push_back(tmp);
	}

	sort(dq.begin(), dq.end());
	
	vector<int> v;
	while (!dq.empty()) {
		v.push_back(dq.front() + dq.back());
		dq.pop_front(); dq.pop_back();
	}

	sort(v.begin(), v.end());
	cout << v[0];
	return 0;
}

5. 소감

• 0-1 BFS를 최근해 구현해봐서, 문제를 보자마자 바로 접근 방법이 떠올랐다.
• 역시 알고리즘은 꾸준함과 많은 경험이다..