[PS] 백준 #20044. Project Teams

문제 정보

• 난이도: 실버 IV
• 문제 주소: https://www.acmicpc.net/problem/20044
• 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디

 

문제

코딩 프로젝트 수업을 가르치는 수찬이는 프로젝트 팀을 가능하면 공정하게 구성하려고 한다. 프로젝트 팀 하나는 두 명의 학생으로 구성되는데, 각 학생들의 코딩 역량은 모두 다르다. 각 학생은 한 팀의 팀원이어야 한다. 공정성을 높이기 위해 수찬이는 팀원 코딩 역량의 합을 최대한 일정하게 유지하려고 한다. 학생들이 코딩 역량이 주어졌을 때 수찬이가 팀을 구성하는데 도움이 되는 프로그램을 작성하라.

문제를 간단하게 하기 위해, 학생 수는 2n이라 가정하자 (n은 양의 정수). 각 학생 si의 코딩 역량은 양의 정수 w(si)로 나타내면 한 i번째 팀 Gi의 코딩 역량은 w(Gi) = ∑s∈Giw(s)로 나타낼 수 있다. 작성할 프로그램 목적은 Sm = min{w(Gi) | 1 ≤ i ≤ n}이 최대화되도록 n개의 팀 G1, G2, …, Gn 을 구성하고 이때 Sm을 출력하는 것이다.

예를 들어, 학생들의 코딩 역량이 {1, 7, 5, 8}로 주어졌다면 (8, 1), (7, 5)로 2개의 조를 짤 수 있으며 프로그램은 9를 출력해야 한다.

 

나의 풀이

일상생활에서도 자주 접할 수 있는 "편차 최소화하기" 개념이다. 즉 이 문제는 그리디하게 가장 큰 값은 가장 작은 값과 매칭시키고, 중간값은 중간값끼리 최대한 매칭을 시켜주면 된다. 따라서 sort를 먼저 해주고, vec[0] + vec[2n-1], vec[1] + vec[2n-2], ... 들 값 중에서 가장 작은 값을 출력하면 된다.

#include <bits/stdc++.h>

using namespace std;

// 84% 틀렸습니다 -> 100001 에서 200001 수정

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

    int n; cin >> n;
    vector<int> vec(2*n);
    for (int i = 0; i < n * 2; i++) {
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());

    int ans = 200001;
    for (int i = 0; i < n; i++) {
        ans = min(ans, vec[i] + vec[2 * n - 1 - i]);
    }
    cout << ans;

}