[BOJ] 13560 축구

문제: https://www.acmicpc.net/problem/13560

 

 

문제 풀이:

4명이 경기를 한다고 가정해보자. (A, B, C, D)

A가 B,C,D를 모두 이긴다면 승점 3

B가 C,D를 이긴다면 승점 2

C가 D를 이긴다면 승점 1

D는 모두에게 졌으므로 승점 0

 

총 승점은 6

 

만약

A가 B,C만 이기면 승점 2

B가 C,D 이기면 승점 2

C가 D 이기면 승점 1

D가 A 이기면 승점 1

 

총 승점은 6

 

즉, 누가 누구를 이기든 총 승점은 (n-1)*n/2가 된다.

 

 

* 총 승점이 (n-1)*n/2이 아니면 항상 유효하지 않지만, 총 승점이 (n-1)*n/2이라고 해서 항상 유효한 것은 아니다.

 

 

입력 받은 각 팀의 점수를 오름차순으로 정렬했을 때, 

2명이 경기 했다면 최소 승점 1이 있어야 하고, 

3명이 경기 했다면 최소 승점 3이 있어야 하고,

4명이 경기 했다면 최소 승점 6이 있어야 한다.

 

문제의 예제를 보자

예제1:

4

0 2 1 3

 

정렬하면 0,1,2,3이 되고,

	1명	2명	3명	4명
총 승점	0	1	3	6
필요한 최소 승점	0	1	3	6

을 만족하니 유효!

 

 

예제 2번:

4

3 3 0 0

 

오름 차순으로 정렬 했을 때, 0 0 3 3이 되고, 

	1명	2명	3명	4명
총 승점	0	0	3	6
필요한 최소 승점	0	1	3	6

2번 째에서 최소 승점 보다 총 승점이 작으므로 유효하지 않다!

 

 

소스 코드:

#include <iostream>
#include <algorithm>
using namespace std;

int n,sum,arr[10002];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		sum += arr[i];
		if (sum < i*(i + 1) / 2) {
			cout << "-1\n";
			return 0;
		}
	}
	if (sum == n * (n - 1) / 2) cout << "1\n";
	else cout << "-1\n";

	return 0;
}