[BOJ 11508] 2+1 세일

3개의 제품을 한 번에 사면 그 중 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 된다. 만약, 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 한다. 이때, 최소비용으로 모든 제품을 구입하면 된다.

 

결국, 무료로 지불하는 금액을 최대화하면 최소비용으로 모든 제품을 구입하는 것과 같다.

최대화하려면 비싼 순서대로 무료로 구입하면 된다. 하지만 3개를 묶어서 그 중 가장 싼 제품만 무료로 구입할 수 있기에, 비싼 순서대로 나열했을 때 3의 배수에 속해있는 것을 제외한 모든 제품의 가격을 더해주면 된다. 

 

반대로 생각하면 모든 가격에서 3의 배수에 속해있는 가격을 제외하면 된다.

long long N, C[MAXN], ans;
int main(void) {
    fastio;
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> C[i], ans += C[i];
    sort(C, C + N, greater<long long>());
    for (int i = 2; i < N; i += 3)
        ans -= C[i];
    cout << ans;
    return 0;
}