[ACM-ICPC][BOJ] 13560 - Football Game 문제풀이

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2016 본선 문제인

BOJ 13560번 Football Game 문제풀이를 해보겠습니다.

---

[문제해석]

N개의 축구팀이 서로 다른 모든 팀과 한 번씩 축구시합을 진행한다. 이때, 이기면 +1점 지면 0점을 얻는다.

이 때, N개의 팀에 대한 승점 리스트가 주어졌을 때, 유효한 리스트면 "1", 아니면 "-1"을 출력하는 알고리즘을 구현하라.

 

[필요한지식]

-Tournament Graph 개념

N개의 팀이 있을 때, 각각의 팀을 노드로 생각하고,

A가 B를 이기면, A에서 B로 가는 방향을 가진 Edge를 추가해 Graph를 만든다고 생각해보자.

A에서 B로 가는 Edge가 있다면, B에서 A로가는 Edge는 존재하지 않을 것이고, N개의 노드가 있을 때, n(n-1)/2 개의 Edge가 생길 것이다. 이런 Graph를 Tournament Graph라고 부른다.

 

-Landau's Theorem

Graph의 노드에 대한 Degree를 오름차순으로 (S1, S2, ⋯ Sn) 으로 정렬했을 때,

다음과 같은 두 성질을 만족한다면, Tournament Graph이다.

 

각 팀의 승점 리스트는 해당 노드의 Degree이므로, 우리는 주어진 승점 리스트로 Landau's Theorem을 이용해 Tournament Graph인지 아닌지 판단하면 된다.

 

#include<cstdio>
#include<algorithm>

int main(void) {
	int ninput, list[10000], sum = 0;
	scanf("%d", &ninput);
	for (int i = 0; i < ninput; i++) {
		scanf("%d", &list[i]);
	}
	std::sort(list, list + ninput);
	for (int i = 0; i < ninput; i++) {
		sum += list[i];
		if (sum < ((i + 1) * i) / 2) {
			printf("-1");
			return 0;
		}
	}
	if (sum == (ninput * (ninput - 1)) / 2)
		printf("1");
	else
		printf("-1");
	return 0;
}

Landau's Theorem을 몰라서 정말 헤매다가 해결한 문제다...

---