[백준/C++] 20044. Project Teams

Greedy

탐욕적 문제 해결 방법
탐욕적 선택을 하더라도 문제의 최적해를 구할 수 있고, 부분 문제의 최적해를 통해 전체 문제의 최적해를 찾을 수 있어야 그리디 알고리즘을 적용할 수 있다.

간단하게 문제를 풀어보자!

20044. Project Teams

문제 난이도 자체는 크지 않다. n개 팀으로 구성하며 인원은 2n명이다. 따라서 2명씩 n개팀으로 나눠주는데, 실력을 정렬해서 가장 못하는(ㅠㅠ)사람과 가장 잘하는 사람으로 팀을 짜주면 된다. 그리디보다는 뭔가 투포인터 느낌이었다.
정렬한 후 맨앞, 맨뒤에서 한칸씩 내려가면서 실력합의 최소를 찾아나간다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n = 0;
vector <int> w;

int main(){

    cin>>n;
    int a;

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

    a = 123456789;

    for(int i = 0; i<n; i++){
        a = min(a, w[i] + w[2*n-i-1]);
    }

    cout<<a<<endl;

    return 0;
}

신촌연합 알고리즘 학회 수업 과제로 나왔던 문제인데, 그 전까지는 C만 쓰다가 여기서 C++의 편리함을 알고 언어를 갈아타게 되었고 로봇개발까지 가게 되었다.
알고리즘 문제를 잘 풀지는 못해서 초급부터 차근차근 풀어가보려고 한다. 화이팅