[백준/BOJ] 1758. 알바생 강호 [Silver 4]

1758. 알바생 강호

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

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, i, tip[100000] = { NULL };
	long long int money = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &tip[i]);
	QuickSort(tip, 0, N - 1);
	for (i = 0; i < N; i++)
	{
		if (tip[i] - i > 0)
			money += tip[i] - i;
		else
			break;
	}
	printf("%lld", money);
	return 0;
}

알고리즘은 이게맞는데, 왜 틀린지 모르겠다.
팁을 가장 많이 받으려면 팁을 많이주는사람 순서대로 줄을세워서 팁을 받는것이다.
다시말해 내림차순으로 정렬후 팁-인덱스를 해주는것이다.

백준에 C언어로 제출을 하면 계속 시간초과가 난다 ㅠㅠ 어떻게 하냐 진짜 다른언어로 갈아타야하나싶다.

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

code

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

int tip[100000] = {};
int main()
{
	int N, i;
	long long int money = 0;
	cin >> N;
	for (i = 0; i < N; i++)
		cin >> tip[i];

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

	for (i = 0; i < N; i++)
	{
		if (tip[i] - i > 0)
			money += tip[i] - i;
		else
			break;
	}

	cout << money;

	return 0;
}