[BOJ] 11508번 2+1 세일 (C++)

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

11508번: 2+1 세일

 

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

int main() {
	int n, c;
	cin >> n;
	vector<int> v;
	for(int i = 0; i < n; i++){
		cin >> c;
		v.push_back(c);
	}
	
	sort(v.begin(), v.end(), greater<>());
	
	int sum = 0;
	for(int i = 0; i < n; i++){
		if((i + 1) % 3 == 0) continue;
		sum += v[i];
	}
	
	cout << sum << endl;
	return 0;
}

 

N개의 가격을 벡터에 담고 내림차순으로 정렬하여 3의 배수번째 수를 제외하고 더한다.

 

예를 들어보면 가격이 [2, 3, 4, 5, 6, 7, 8]일 때

[2] [3 4 5] [6 7 8]

위처럼 큰 수부터 3개씩 묶으면 최대한 비싼 것을 무료로 지불하여 최소비용으로 구입할 수 있다.