[백준/BOJ]16304. A Prize No One Can Win [Silver 5]

16304. A Prize No One Can Win

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

정렬해서 작은순으로 2개씩 더해서 X보다 크게 나오면 break하고, 그 인덱스를 출력하면 될줄알았는데, 46%에서 시간초과로 실패했다...(퀵정렬썻는데...)

code

#include <stdio.h>
void QuickSort(int* arr, int start, int end)
{
	if (start >= end)
		return;
	int piv = start;
	int 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 i, n, X, items[100000] = { 0 }, cnt = 0;
	scanf("%d %d", &n, &X);
	for (i = 0; i < n; i++)
		scanf("%d", &items[i]);
	QuickSort(items, 0, n - 1);
	if (n == 1)
		printf("1");
	else
	{
		for (i = 1; i < n; i++)
			if (items[i - 1] + items[i] > X)
				break;
		printf("%d", i);
	}
	return 0;
}

C++로 풀었다. 알고리즘은 동일하게 적용했다.

code

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

int items[100000];
int main()
{
	int i, n, X, cnt = 0;
	cin >> n >> X;
	for (i = 0; i < n; i++)
		cin >> items[i];

	sort(items, items + n);

	if (n == 1)
		printf("1");
	else
	{
		for (i = 1; i < n; i++)
			if (items[i - 1] + items[i] > X)
				break;
		printf("%d", i);
	}
	return 0;
}