[백준/c++] BOJ 11508 - 2+1세일

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

11508번: 2+1 세일

 

문제 설명

편의점에서 2+1 세일을 진행한다.

한번의 3개의 유제품을 살 경우에만, 그 중에서 가장 값이 싼 것을 무료로 지불한다.

총 N팩의 유제품을 구입하려고 할 때, 유제품을 모두 살 때 필요한 최소비용을 출력한다.

유제품의 수 N과 각 유제품의 가격 Ci가 주어진다.

N (1 <= N <= 100,000)

Ci (1 <= Ci <= 100,000)

 

해결

N개의 유제품을 세개씩 묶었을 때, 가장 값이 싼 것을 무료로 얻을 수 있다.

무료로 얻는 유제품의 가격이 비싼 것일 수록 이득을 보게 되는데, 따라서 가장 비싼 것부터 정렬하여 순서대로 3개씩 묶어 주면 된다.

 

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n;
vector<int> v;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	
	sort(v.rbegin(), v.rend());
	int ans = 0;
	for (int i = 0; i < n; i+=3) {
		ans += v[i];
		if (i + 1 < n) ans += v[i + 1];
	}
	cout << ans;
}