4050. 재관이의 대량 할인

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIseXoKEUcDFAWN&categoryId=AWIseXoKEUcDFAWN&categoryType=CODE

SW Expert Academy

 

 

처음엔 무턱대고 3개씩 DFS로 선출하려 했지만 N값으로 10만개가 들어올 수 있다는 것을 보고, 

시간초과가 발생할 것이라고 판단하여 다른 방식을 생각해 보았다.

한 그룹내에서 최소를 제외했을 때 가장 큰 이득을 얻으려면 제외되는 값이 큰 값이면 된다.

그 값이 큰 값이려면 그보다 더 큰 수 2개와 함께 그룹을 지으면 된다. 

즉, 내림차순 정렬하여 3의 배수 인덱스에 속하는 것들만 제외시키면 끝.

 

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

int N;
int arr[100001];
bool compare(int a, int b)
{
	return a > b;
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{

		cin >> N;
		int sum = 0;
		for (int i = 1; i <= N; i++)
		{
			cin >> arr[i];
			sum += arr[i];
		}

		sort(arr+1, arr + N+1, compare);
		
		int idx = 1;
		while (idx <= N)
		{
			if (idx % 3 == 0)
			{
				sum -= arr[idx];
			}
			idx++;
		}

		cout << "#" <<test_case << " " << sum << endl;
		
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}