문제 개요
n개의 요소를 가진 배열 A와 하나의 숫자 s가 주어진 상황을 가정해 보겠습니다. 탁자 위에는 텅 빈 물컵 하나와 물이 담긴 물컵 n개가 놓여 있으며, 이 게임에는 여러 명의 플레이어가 참여합니다. 각 턴마다 플레이어는 물이 든 컵 하나를 골라 그 안의 물을 전부 빈 컵에 부어야 하고, 물이 넘쳐흐르면 해당 플레이어는 패배합니다. 따라서 우리가 확인해야 할 것은 모든 플레이어가 승자가 될 수 있는지, 즉 컵이 넘치지 않는지 여부입니다. 단, 컵이 이미 가득 차 있다면 다음 플레이어는 자신의 턴을 진행하지 않습니다. 여기서 s는 빈 컵의 용량이며, A[i]는 i번째 컵에 담긴 물의 양을 의미합니다.
예를 들어 입력이 A = [3, 1, 3], s = 4라고 가정해 봅시다. 이 경우 출력은 True입니다. 첫 번째와 두 번째 플레이어가 차례로 물을 부으면 컵이 정확히 가득 차기 때문입니다. 이후 마지막 플레이어는 컵이 이미 가득 차 있으므로 턴을 진행하지 않고 그대로 승자가 됩니다.
해결 단계
이 문제는 다음 절차를 따라 해결할 수 있습니다.
k := 0
n := 배열 A의 크기
배열 A를 오름차순으로 정렬
i := 0으로 초기화한 뒤, i < n - 1을 만족하는 동안 i를 1씩 증가시키며 반복:
k := k + A[i]
만약 k > s라면:
false 반환
그렇지 않으면:
true 반환핵심 아이디어는 배열을 오름차순으로 정렬한 후, 가장 큰 값을 제외한 나머지 n-1개 원소의 합(k)을 컵의 용량(s)과 비교하는 것입니다. 작은 컵들부터 물을 부어 컵을 가득 채우면 마지막 플레이어는 턴을 건너뛰게 되므로, 이 합이 용량 이하일 때 모든 플레이어가 승리할 수 있습니다. 정렬 과정이 포함되므로 전체 시간 복잡도는 O(n log n)입니다.
예제 코드
아래의 C++ 구현 예제를 통해 더욱 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A, int s){
int k = 0;
int n = A.size();
sort(A.begin(), A.end());
for (int i = 0; i < n - 1; i++)
k += A[i];
if (k > s)
return false;
else
return true;
}
int main(){
vector<int> A = { 3, 1, 3 };
int s = 4;
cout << solve(A, s) << endl;
}입력
{ 3, 1, 3 }, 4
출력
1
출력값 1은 true, 즉 모든 플레이어가 승자가 될 수 있음을 의미합니다.