# [Gold I] Beast Bullies [문제 링크](https://www.acmicpc.net/problem/27384) ## 문제 설명 <p>There are some animals with distinct strength levels getting water from a watering hole. The more animals that are at the watering hole the less water each animal will get. For this reason some of the animals will try to force the others to leave.</p> <p>Periodically the weakest animal in the group may be attacked by some of the stronger animals. Other animals may come to the aid of the weakest animal. The weakest animal will leave if the sum of the strength levels of the attackers is strictly greater than the sum of the strength levels of the defenders. The other defenders, if any, will remain. This may repeat any number of times.</p> <p>As an up-and-coming zoologist, you are interested in determining if animals are logical thinkers. You have a lot of data, so you will write a program to help check if, in each situation, the animals behaved optimally. Each animal wants to eliminate as many other animals as possible without being eliminated itself.</p> <p>Given the strength level of each animal and assuming each animal always makes the best decision for their best interests, determine how many animals are guaranteed to remain after all aggression has been resolved.</p> ## 입력 <p>The first line of input contains a single integer $n$ ($1 \le n \le 5 \times 10^5$), which is the number of animals.</p> <p>Each of the next $n$ lines contains a single integer $s$ ($1 \le s \le 10^9$). These are the strengths of the animals. No two strengths will be the same.</p> ## 출력 <p>Output a single integer, which is the number of animals guaranteed to remain.</p> ## 풀이 게임에서의 최선의 선택은 자신이 살면서 자신 앞에 있는 최대한 많은 수의 동물들을 죽이는 것입니다. 정렬해서 뒤에서부터 범위를 늘려가며 자신이 공격자와 방어자 중 어디에 속해야 하는지 그리디하게 보면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> v(n); for(int i=0;i<n;i++) cin >> v[i]; sort(v.begin(), v.end()); ll attackIdx=n-1, attacker=v[n-1], defender=0; for(int i=n-2;i>=0;i--) { defender += v[i]; if(defender>=attacker) { attacker += defender; defender=0; attackIdx=i; } } cout << n-attackIdx; } ```