[C++] 11508. 2+1세일

그리디 문제이다.

2+1으로 3개중 가장 작은 값을 무료로 해주기 때문에 가능한 큰 숫자들끼리 묶어서 가장 작더라도 전체에서는 큰 숫자를 무료로 받도록 코드를 짰다.

 

1. 내림차순으로 정렬
2. 3개씩 묶어서 마지막 값은 sum에 포함 안해준다. (인덱스가 0부터 시작하므로 i%3이 2가 아니면 다 더해줌)

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int N;
    vector<long long> c;

    cin >> N;
    for(int i=0; i<N; i++) {
        int t; cin >> t;
        c.push_back(t);
    }

    sort(c.begin(), c.end(), greater<int> ());
    long long sum = 0;
    for(int i=0; i<N; i++) {
        if(i%3 != 2) sum += c[i];
    }

    cout << sum << "\n";

    return 0;
}