[백준/BOJ]11508. 2+1 세일[Silver 4]

11508. 2+1 세일

문제출처 : https://www.acmicpc.net/problem/11508

code

#include <stdio.h>
void QuickSort(int arr[],int start,int end)
{
	if (start >= end)
		return;
	int piv = start, left = start + 1, right = end, temp;
	while (left <= right)
	{
		while (left <= end && arr[left] >= arr[piv])
			left++;
		while (right > start && arr[right] <= arr[piv])
			right--;
		if (left > right)
		{
			temp = arr[right]; arr[right] = arr[piv]; arr[piv] = temp;
		}
		else
		{
			temp = arr[left]; arr[left] = arr[right]; arr[right] = temp;
		}
	}
	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
int main()
{
	int N, C[100000] = { 0 }, i, total = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &C[i]);
	QuickSort(C, 0, N-1);
	for (i = 0; i < N; i++)
		if (i % 3 != 2)
			total += C[i];
	printf("%d", total);
	return 0;
}

최대로 할인받기위해서는 내림차순으로 정렬후 3번째 인덱스를 제외한 모든 값을 더하면 된다.
(3번째는 무료이기때문)
근데 계속 시간초과가 난다....

C++로 해결하였다. 알고리즘은 동일하다.

code

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

int main()
{
	ios::sync_with_stdio(false);

	int N, C[100000] = { 0 }, i, total = 0;

	cin >> N;
	for (i = 0; i < N; i++)
		cin >> C[i];

	sort(C, C + N, greater<>());

	for (i = 0; i < N; i++)
		if (i % 3 != 2)
			total += C[i];

	cout << total;

	return 0;
}