[BOJ 13560] 축구 게임

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

13560번: 축구 게임

 

- 문제 요약

 

축구는 지구에서 가장 인기 있는 스포츠 중의 하나입니다. n 팀으로 이루어진 축구 리그가 있습니다. 하나의 팀은 다른 모든 팀과 정확히 한 번씩만 경기를 합니다. 그러므로, 각 팀은 n - 1번의 경기를 하게 됩니다. 무승부는 승부차기를 하기 때문에 없습니다. 한 경기 후에 이긴 한 팀은 1 점을 얻게 되고, 진 팀은 0 점을 얻게 됩니다.

베스트 팀 선정을 위해 경기 일정이 끝난 후에 각 팀은 리그 사무소에 획득한 점수를 보고하게 됩니다. 리그 사무소는 각 팀이 보고한 점수가 실수가 없는지 확실히 해두고 싶습니다. 즉, 보고한 점수가 유효한지 아닌지 알고 싶은 것이고, 이 말은 리그 룰에 따르는 경우 이 점수들을 각 팀에 할당하는 것이 가능해야 합니다.

주어진 n 개의 정수들은 각 팀에서 보고한 점수들로 이 점수들이 유효한지 아닌지 알아내는 프로그램을 작성해야 합니다.

프로그램은 표준 출력에 써야 합니다. 보고한 점수들이 유효한 경우라면 1을 출력하고, 그렇지 않으면 -1을 출력합니다.

 

 

- 알고리즘 정리

 

문제에서 n개의 팀이 각각 n-1번의 경기를 하게 된다고 했으니, 점수의 총합은 n * ( n - 1 ) / 2가 될 것입니다.

입력으로 들어오는 점수를 오름차순으로 정렬하고 현재까지의 i개의 총합이 i * ( i - 1 ) / 2보다 작다면 유효하지 않은 경우이므로 -1을 출력해주고, 그게 아니라면 sum 변수의 값과 점수의 총합을 비교해서 동일 여부를 따져주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 10001
int n,arr[MAX],sum;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	sort(arr+1,arr+1+n);
	for(int i=1;i<=n;i++){
		sum+=arr[i];
		if(sum<i*(i-1)/2){
			cout<<-1;
			return 0;
		}
	}
	cout<<(sum==n*(n-1)/2?1:-1);
}

코드 제출 결과