[그리디 #9] BOJ 11508 - 2+1 세일

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

11508번: 2+1 세일

 

접근 방법

3개씩 묶어서 구매할 때, 가장 싼 제품을 무료로 준다는 것이 핵심이다.

 

금액을 최소로 만들기 위해서는 가장 싼 제품으로 가격이 꽤 나가는 제품이 선정되어야한다.

이를 위해선 나머지 두 제품이 가장 비싼 제품으로 선정되어야 한다는 것이다.

 

다시 말해, 금액을 내림차순으로 정렬 후, 3개씩 묶어서 구매하면 된다.

 

정석적인 그리디 접근법으로 다가가면 쉽게 풀 수 있는 문제이다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX 100001

int n;
vector<int> v;

bool cmp(int a, int b) {
	return a > b;
}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	
	sort(v.begin(), v.end(), cmp);


	
	long long sum = 0;
	for(int i = 0; i < n;) {
		if (i + 3 <= n) {
			sum += (v[i] + v[i + 1]);
			i += 3;
		}
		else {
			//cout << "v[i] : " << v[i] << endl;
			sum += v[i];
			i++;
		}
		
	}
	cout << sum;

}