[11508] 2+1 세일

https://www.acmicpc.net/problem/11508

11508번: 2+1 세일

 

<문제>

N개의 물건의 가격이 들어올때, 물건을 최대 3개까지 하나의 집합으로 분할이 가능하다.

3개의 원소로 이루어진 집합일때, 가장 싼 물건은 값을 지불하지 않아도 된다.

이때 지불할 비용을 최소화하는 문제다.

 

answer = (전체 가격의 합) - (할인받은 가격의 합) 이다.

전체 가격의 합은 고정이므로 answer를 최소화하기 위해서, 할인받을 가격을 최대화해야한다.

 

그렇다면 가장 비싼값을 할인받는다는 생각을 먼저 할 수 있겠다.

아래의 경우를 보자

input = {1, 2, 3, 4, 5}

여기에서 할인을 받는것이 가능한 경우는 {1, 2, 3}밖에 없다.

4나 5의 경우, 이를 각각 할인받기 위해서는 이보다 더 큰 물건이 최소한 2개는 존재해야 하지만

input에서는 4보다 큰 물건이 1개, 5보다 큰 물건이 0개로 이를 할인받기는 불가능하다.

 

위의 경우에서 보듯, 3번째로 큰 물건부터 순차적으로 할인받는다고 생각하면 된다.

 

<소스코드>

#include<stdio.h>
#include<algorithm>
using namespace std;
int sum, n, a[100001];
int main(void) {
    int i, j;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    sort(a, a + n, greater<>());
    for (i = 0; i < n; i++)
        if (i % 3 != 2)
            sum += a[i];
    printf("%d", sum);
    return 0;
}

내림차순 정렬하고, 3번째 물건은 포함시키지 않으면서 누적해 출력해주었다.