[마이다스챌린지2017예선] 세일이벤트 문제

세일이벤트 문제 (SaleEvent)

영희는 길을 걷다가 2개를 사면 1개를 공짜로 주는 이벤트를 진행하고 있는 가게를 발견하였습니다. 다만 공짜 이벤트에는 조건이 있는데, 연속해서 진열된 3개를 한 그룹으로 묶어서 그 중 가장 싼 1개를 공짜로 주는 것입니다.

예를 들어 가격이 8, 15, 16, 12, 20, 18, 16, 15 인 물건들을 전부 구매하고자 할 때(총 가격 120) 아래와 같이 묶어서 가격을 살펴볼 수 있습니다. (아래 외에도 다양하게 3개씩 묶을 수 있습니다)

(8, 15, 16), (12, 20, 18), 16, 15 → 8, 12를 할인 받아 총 100

8, (15, 16, 12), 20, (18, 16, 15) → 12, 15를 할인 받아 총 93

8, (15, 16, 12), (20, 18, 16), 15 → 12, 16을 할인 받아 총 92 (가장 싼 가격)

(8, 15, 16), 12, 20, (18, 16, 15) → 8, 15를 할인 받아 총 97

위에서 보다시피, 진열된 물건들을 어떻게 그룹으로 묶냐에 따라서 총 가격이 달라질 수 있습니다. 또한 필요한 경우, 그룹을 묶지 않을 수도 있습니다. 가격이 1, 2, 7, 8, 10, 2 인 물건들의 경우, 1, 2, (7, 8, 10), 2 로 묶어서 7원을 할인 받고 나머지는 그냥 구매하는 것이 좋은 선택입니다. 또, 동일한 가격의 제품끼리 묶이는 경우에는 가장 싼 가격의 제품 중 하나만 무료입니다. 1, (2, 10, 2) 의 경우에는 13원을 지불하게 됩니다.

충동적으로 영희는 이 가게의 모든 물건들을 구매하기로 했습니다. 이 때 영희를 도와서 물건들을 가장 싸게 살 방법을 찾아주는 프로그램을 작성하십시오.

입력

입력은 표준 입력(stdin)으로 주어지며

첫째 줄에는 물건의 개수 N (3 <= N <= 2000)이 주어집니다.

둘째 줄에는 N개에 대한 가격이 공백으로 구분되어 주어집니다. ( 1<= 가격 <= 1000 )

모든 입력은 주어진 범위를 넘어가지 않는 정수로 주어집니다.

출력

출력은 표준 출력(stdout)으로 이루어지며,

첫째 줄에 가장 싸게 살 수 있는 가격을 출력합니다.

입력예)

8

8 15 16 12 20 18 16 15

출력예)

92

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

int main()
{
	int count;
	cin >> count;
	vector<int> vinput;

	for (int c = count; c; c--)
	{
		int input;
		cin >> input;
		vinput.push_back(input);
	}

	int total = std::accumulate(vinput.begin(), vinput.end(), 0);
	vector<int> minarray;

	int maxValue = 0;
	for (int i = 0; i < count - 2; i++)
		minarray.push_back(*std::min_element(vinput.begin() + i, vinput.begin() + i + 3));

	for (int i = 0; i < count - 2; i++)
	{
		maxValue = std::max(maxValue, minarray[i]);
		for (int j = i + 3; j < count - 2; j++)
			maxValue = std::max(maxValue, minarray[i] + minarray[j]);
	}

	cout << total - maxValue;
	return 0;
}