[BOJ | 백준] 13560번: 축구 게임

by Kimcoding on 2020-03-13 02:50

in BOJ

문제 설명

BOJ 13560

축구 경기를 한 팀의 점수가 주어졌을 때 유효한 점수인지 확인하는 문제입니다.

풀이

모든 경우를 확인하기에 너무 많은 경우의 수가 있습니다.

일단 점수가 유효하려면 모든 팀이 서로 한번씩 경기를 하여 한 팀이 1점을 얻기 때문에

모든 점수의 총합이 N * (N - 1) / 2이어야 합니다.

그 다음 제가 생각한 방법은 가장 낮은 점수를 가진 사람들 X명이 모여서

점수를 합했을 때 X * (X - 1) / 2보다 작다면 유효할 수 없습니다.

X명이 경기를 하여 X * (X - 1) / 2의 점수가 나오기 때문에

적어도 점수의 총합이 이 값이 나와야합니다.

사실 문제를 대충보고 때려맞췄는데 맞았습니다…

정확한 증명을 원하여 찾아봤는데 ‘랑주의 정리’라고 합니다.

자세한 증명은 밑 링크를 클릭해주세요!

Landau’s Theorem

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i, a, b) for(int i=a;i<=b;i++)
using namespace std;

int main() {
	FIO;
	int n, sum = 0;
	int v[10005];
	cin >> n;
	FOR(i, 1, n) cin >> v[i];
	sort(v + 1, v + n + 1);
	FOR(i, 1, n) {
		sum += v[i];
		if (sum < i * (i - 1) / 2)
			return cout << -1 << '\n', 0;
	}
	cout << (sum == n * (n - 1) / 2 ? 1 : -1) << '\n';
	return 0;
}