백준 13560 축구게임 c++

문제

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

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

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

입력

프로그램은 표준 입력에서 읽어야 합니다. 입력은 두 줄로 이루어져 있고, 첫째 줄은 하나의 정수 n (2 ≤ n ≤ 10,000) 이고, 팀의 개수를 의미합니다. 다음 줄은 각 팀에서 보고한 점수들입니다. 각 정수는 0 보다 같거나 크고 n - 1 보다 같거나 작습니다.

출력

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

예제 입력 1 복사

4
0 2 1 3

예제 출력 1 복사

1

예제 입력 2 복사

4
3 3 0 0

예제 출력 2 복사

-1

 

 

 

내 tistory 블로그에 처음 쓰는 플레티넘 문제인듯하다.

최근에 마의벽인 골드1에서 플레티넘을 찍게 되었고 플레 그리디 문제들을 풀고 있는데 플레 그리디 문제집을 만드신분이 모은 문제들만 그런지는 모르겠지만 골드 그리디에 비해서 로직이 너무 어렵거나 코드 구현이 너무 어려운 그런 느낌은 아닌것같다. 다만 골드 문제들은 생각을 깊이 한다면 풀 수 있는 정도라면 플레 난이도 그리디는 새로운 알고리즘이나 방법론을 도입해서 풀어야 하는 느낌이 강하다.

 

 

이 문제는 Tournament Graph에 대한 개념과 Landau's Theorem에 대한 이해를 요구한다.

 

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라고 한다.

 

2. Landau's Theorem? (란다우의 정리)

Graph의 노드에 대한 Degree를 오름차순으로 (s1,s2,...sn)으로 정렬했을 때, 다음과 같은 두 성질을 만족한다면, Tournament Graph이다.

 

 

이 로직들을 문제에 적용한다면

1. 배열에 경기내용들을 입력 받는다.

2. 경기내용을 오름차순으로 정렬해 준다.

3. 각 경기마다 란다우의 정리를 이용해 Tournament Graph가 만족하지 않으면 -1을 출력하고 종료한다.

4. 모든 경기에 대한 합이 란다우의 정리를 만족하면 1 아니면 -1 출력

 

 

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


int n;

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;


    int arr[100001];

    for(int i = 0 ; i < n; i++){
        cin >> arr[i];
    }

    sort(arr,arr+n);
    
    int sum=0;

    for(int i = 0 ; i < n ; i ++){

        sum+=arr[i];

        if(sum<((i+1)*i/2) ){
            cout<<-1;
            return 0;
        }

    }

    if(sum == (n * (n-1))/2)
        cout << 1;
    else
        cout << -1;

    return 0;


}