13560번: 축구게임

13560번: 축구게임 - 탐욕법

하나의 팀은 다른 모든 팀과 정확히 한 번씩만 경기를 하고 무승부는 없을 때의 팀별 승수가 주어졌을 때

유효한 조합인 지 파악하는 문제이다.

O(N)에 푸는 방법은 아래와 같다.

Fulkerson Chen Anstee theorem

: i는 1부터 N까지 일 때, ΣA[i] ≤ i*(i-1)/2 이며, ΣA[i] = N*(N-1)/2 이여야한다.

위를 만족할 경우 1, 아닐 경우 -1을 출력해주면 되는 문제이다.

또한 탐욕법으로 O(N^2)에 풀 수도 있는데

매 단계마다 승수가 가장 높은 팀은 승수가 낮은 팀에 대해 이긴다라는 방법을 선택하여

모든 팀에 대하여 진행해주면 풀 수 있는 문제이다.