https://www.acmicpc.net/problem/20044
20044번: Project Teams
입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로
www.acmicpc.net
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 사용법
728x90
'Problem Solving > 백준' 카테고리의 다른 글
[백준/c++] 14042 - Tandem Bicycle (0) | 2021.04.25 |
---|---|
[백준/c++] 20551 - Sort 마스터 배지훈의 후계자 (0) | 2021.04.24 |
[백준/c++] 11728 - 배열 합치기 (0) | 2021.04.24 |
[백준/c++] 19637 - IF문 좀 대신 써줘 (0) | 2021.04.23 |
[백준/c++] 21313 - 문어 (2) | 2021.04.18 |