문제
현식이는 물고기를 키우고 있습니다. 물고기들은 각각의 길이를 가지고 있습니다.
이 물고기들은 온순해 보이지만, 사실 자기들끼리 살생을 일삼는 무서운 존재들입니다. 이것을 알아챈 현식이는, 물고기를 관찰하여 다음과 같은 사실을 알아냈습니다.
[임의의 물고기 A에 대해, A의 길이보다 짧은 물고기들의 길이의 합이 A의 길이보다 짧을 경우 A가 그들을 전부 잡아먹어 버린다.]
당연하게도, 길이가 가장 짧은 물고기는 다른 물고기를 먹지 못합니다.
평화주의자 현식이는 물고기 몇 마리를 더 투입시켜서 살생이 일어나지 않도록 하려 합니다. 현식이가 투입해야 하는 물고기의 최소 마릿수를 출력해 주세요.
입력
첫째 줄에 물고기의 수인 N(2<=N<=100,000)이 주어집니다.
둘째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
i번째 수는 i번째 물고기의 길이(길이<=10,000 정수)입니다.
<제약사항>
서브태스크 1 : N≤1,000. 모든 물고기의 길이≤1,000. 전체 데이터의 60%
서브태스크 2 : N≤100,000. 모든 물고기의 길이≤10,000.
출력
첫째 줄에 현식이가 투입시켜야 할 물고기의 최소 마릿수를 출력합니다.
예제 #1
2
2 5
2
길이가 2와 4인 물고기를 투입시킬 경우 물고기의 길이는 각각 2, 2, 4, 5이고 모든 물고기는 서로를 잡아먹지 못합니다.
예제 #2
4
20 1 71 28
5
출처
cki86201
로그인해야 코드를 작성할 수 있어요.