[백준/BOJ] 1448. 삼각형 만들기 [Silver 3]

1448. 삼각형 만들기

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

code

#include <stdio.h>
#include <stdlib.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[right];
			arr[right] = arr[left];
			arr[left] = temp;
		}
	}
	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
int main()
{
	int N, i, sum = -1;
	int* arr;
	scanf("%d", &N);
	arr = (int*)malloc(N * sizeof(int));
	for (i = 0; i < N; i++)
		scanf("%d", &arr[i]);
	QuickSort(arr, 0, N - 1);
	for (i = 0; i < N - 2; i++)
		if (arr[i] < arr[i + 1] + arr[i + 2])
		{
			sum = arr[i] + arr[i + 1] + arr[i + 2];
			break;
		}
		printf("%d", sum);
	free(arr);
	return 0;
}

이게 테스트케이스가 백만인경우 퀵소트 시간복잡도에서 걸리는것같다...
테스트케이스가 많을때 시간초과되는 경우가 많은데, 이걸 어떻게 해결하면좋을까? ㅠㅠ

C++로 해결하였다. 알고리즘은 동일하게 적용시켰다.

code

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

int arr[1000000] = {};
int main()
{
	int N, i, sum = -1;

	cin >> N;
	
	for (i = 0; i < N; i++)
		cin >> arr[i];
	
	sort(arr, arr + N,greater<>());

	for (i = 0; i < N - 2; i++)
		if (arr[i] < arr[i + 1] + arr[i + 2])
		{
			sum = arr[i] + arr[i + 1] + arr[i + 2];
			break;
		}

	cout << sum;

	return 0;
}