[c++][그리디] 백준 11508번: 2+1 세일

 

 

 

 

 

 

 

문제풀이

1. 유제품 가격을 배열로 저장하여 내림차순으로 정렬을 한다.

2. 내림차순으로 나열된 유제품 가격을 순서대로 3개씩 나눴을 때 세 번째의 가격만 제외하고 모두 더한다.

예) 10, 9, 4, 2, 6, 4, 3

내림차순으로 정렬 -> 10, 9, 6, 4, 4, 3, 2

정렬된 내림차순에서 3개씩 나눠서 생각 -> 10, 9, 6 / 4, 4, 3 / 2

세 번째의 가격만 제외했을 경우 -> 10, 9, 6 / 4, 4, 3 / 2

세 번째의 가격만 제외하고 더하기 =>10, 9, 4, 4, 2만 더하면 최소 비용(=29)으로 유제품을 구입할 수 있다.

 

 

 

코드

#include <iostream>
#include <algorithm>

#define MAX 100000

using namespace std;

bool compare(int i, int j) {
	return i > j;
}

int main() {
	int n;
	int price[MAX];

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> price[i];
	}

	sort(price, price + n, compare);

	long long result = 0;

	int temp = 2;

	for (int i = 0; i < n; i++) {
		if (temp == i) {
			temp += 3;
			continue;
		}
		result += price[i];
	}

	cout << result;

	return 0;
}