백준 22993: 서든어택 3(python)

문제

늘 생각하는 거지만 백준 사이트는 사족이 달린 문제가 참 많은 것 같다;

---

풀이

 

"좋은 전투 순서가 존재"한다는 가정이 핵심이다. 전투 순서가 지정되지 않았으니 준원이에게 유리한 최적의 전투 순서 하나만을 상정하고, 그 순서에서도 준원이가 승리하지 못한다면 다른 모든 경우의 수에서도 승리하지 못할 것이라 생각하는 것이다. 준원이를 제외한 플레이어들을 공격력에 따라 오름차순 정렬한 뒤, 준원이 혼자 약한 플레이어부터 하나씩 공격하며 공격력을 누적해 나가는 방식이 준원이에게 가장 유리한 전투 순서이다.

 

이 과정을 pseudocode로 나타내면 다음과 같다.

준원이를 제외한 플레이어들에 대해:
	준원 > 플레이어인 경우:
    	준원이의 공격력 갱신(+= 플레이어)
    준원 < 플레이어인 경우:
    	준원이 사망, "No"
	준원 == 플레이어인 경우:
    	아무 일도 일어나지 않지만, 앞으로 만날 플레이어들을 이길 수 없으므로 결국 "No"
"Yes"

중간에 한 번이라도 공격력이 같거나 강한 플레이어를 만나지 않은 채로 for문을 빠져나올 경우 다른 모든 플레이어를 죽일 수 있다는 의미이므로 "Yes"를 출력하고 종료한다.

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
if N == 1:
    print("Yes")
    sys.exit(0)

arr = list(map(int, input().split()))
jw = arr[0]
ordered = sorted(arr[1:])

for i in range(N - 1):
    if jw > ordered[i]:
        jw += ordered[i]
    else:
        print("No")
        sys.exit(0)
print("Yes")