[백준/BOJ]22993. 서든어택3 [Silver 4]

22993. 서든어택3

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

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

내 생각에 알고리즘은 이게 맞는것 같은데 왜 틀리는지 모르겠다. 어쨋든 준원이가 최후의 생존자가 되려면 다른경쟁자를 모두이겨야하기 때문에 모두를 이길수 있는 좋은 전투순서는 A2~AN(A1은 준원이) 까지 약한순서대로 오름차순정렬을해서 한명씩 이기면서 공격력을 올리는 것이다.

그리고 출력이 조금 애매한게, 전투가 어떤 순서로 이루어져도 준원이가 절대 최후의 생존자가 될 수 없다면 No를 출력 공격력이 같으면 아무일도 안일어나는데, 어쨋든 준원이가 최후의 생존자면 Yes를 출력해도 되는지 이해가 잘안된다.
예를들어
3
1 1 1이면, 아무일도 안일어나긴하지만, 어쨋든 준원이는 최후의 생존자 이기때문에 Yes인지 No인지 헷갈린다... 내가멍청한걸수도있다
여튼 이문제가 올라온지 얼마 안됐기 때문에 업데이트가 덜된걸 수도 있는데 일단 나는 이게 최선의 답이라고 생각한다.

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

code

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

long long A[100001];
int main()
{
	int N, i;
	cin >> N;
	cin >> A[0];
	for (i = 1; i < N; i++)
		cin >> A[i];

	sort(A+1,A+N);

	for (i = 1; i < N; i++)
	{
		if (A[0] > A[i])
			A[0] += A[i];
		else
		{
			printf("No");
			return 0;
		}
	}
	printf("Yes");

	return 0;
}