[13560] 축구 게임

백준 링크

내가 생각한 풀이

일단 리그전으로 진행되므로 n(자연수)개의 팀이 진행될 때, input으로 입력된 값들의 합은 n x (n-1) / 2의 값이다.
여기서 나는 n보다 작은 i개의 팀이 존재할 때 그 i개의 팀이 존재할 수 있는 최소의 경기 수가 (i-1) x i / 2를 만족해야만 한다고 조건을 세워서 코드를 작성했다.
이건 단순히 내 직관이기 때문에 자세한 증명이 필요해서 찾아보았다.

#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAX 10000
using namespace std;

int main(){
   int n, sum=0, arrSum=0;
   int arr[MAX];

   scanf("%d",&n);
   for(int i=0;i<n;i++){
      scanf("%d",&arr[i]);
      sum+=arr[i];
   }
   sort(arr, arr+n);
   int conSum = n*(n-1)/2;
   for(int i=0;i<n;i++){
      arrSum += arr[i];
      if(arrSum<i*(i+1)/2){
         printf("-1\n");
         return 0;
      }
   }
   int num = sum==conSum? 1 : -1;
   printf("%d\n",num);

}

정답

1. '랑주의 정리'라는 알고리즘을 이용한 방법이었다.
   
   자세한 증명 방법이 알고 싶다면 아래 링크로 들어가면 된다.
   설명 자료
   시간복잡도는 O(N)이다.

2. 그 외에 그리디 알고리즘을 이용해 하나씩 비교하면서 계산하는 방법도 있다.
   시간복잡도는 O(N^2)이다.