BOJ)13560 Football

문제: icpc.me/13560 

n개의 축구 팀이 존재할 때 각 축구 팀의 승수가 주어진다. 각 축구팀들 끼리는 무조건 한번의 경기가 열리며 승패가 반드시 갈린다고 할 때 주어진 축구팀의 승수의 셋이 valid 한지의 여부를 묻는 문제이다.

우리는 승수를 받은 뒤 sort해준 다음 승수가 적은 팀부터 큰 팀으로 볼 건데 승수가 작은 팀은 승수가 현재 주어진 셋에서 큰팀한테 졌다고 가정하여 팀을 하나씩 삭제하는 방법으로 그리디하게 접근해줄 것이다.

도중에 내가 이긴팀이 남은 팀보다 많거나 내가 이긴팀의 수가 0보다 작은 경우가 생기면 invalid하다고 판단해주면 된다.

#include <cstdio>
#include <algorithm>
#define MAX_N 10000
using namespace std;
int c[MAX_N + 1], n, f;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    sort(c + 1, c + 1 + n);
    for (int i = 1; i <= n; i++) {
        if (c[i] > n - i || c[i] < 0) {
            f = 1;
            break;
        }
        for (int j = 0; j < n - c[i] - i; j++)
            c[n - j]--;
        sort(c + i + 1, c + 1 + n);
    }
    printf("%d\n", f ? -1 : 1);
    return 0;
}