[백준 13560번] 축구 게임 (Python3)

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을 출력한다.

 

 

오늘의 교훈) 그리디 알고리즘 문제는 어렵다