def solve():
if sum(win) != N*(N-1)//2:
return -1
upset = 0
for i in range(N):
upset += win[i]-i
if upset < 0:
return -1
return 1
N = int(input())
win = sorted(map(int,input().split()))
print(solve())
그리디 알고리즘 문제
아이디어를 떠올리지 못하여, 질문게시판에서 힌트를 얻어 해결하였다. (참고 https://www.acmicpc.net/board/view/72090)
풀이를 설명하면,
1. 승리수가 N(N-1)/2가 아니라면 당연히 -1이다.
2. 승리수를 오름차순으로 정렬한다.
3. i번째 팀에 대해서, 현재 팀보다 못하는 팀을 모두 이긴다고 가정한다. (즉, win[i]==i)
4. 3에서 만약 횟수가 차이가 난다면 (win[i] != i), 순위가 더 낮은 팀이 높은 팀을 이겼다는 뜻이므로 upset 횟수를 갱신한다.
5. 만약 과정에서 upset 횟수가 음수가 된다면, 불가능한 경우이므로 -1을 출력한다.
오늘의 교훈) 그리디 알고리즘 문제는 어렵다