[백준] 13560번 축구 게임 Java

문제 링크

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

문제

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

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

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

입력

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

출력

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

알고리즘: 그리디, 수학

풀이

먼저 세 가지 정의할 것이다.

1. 승점은 오름차순으로 정렬돼있음
2. 현재 팀은 앞으로 나올 모든 팀을 이긴다고 가정함.
3. 총 승점은 N(N-1)/2이다.
   ex) 4팀 중 한 팀이 다 이기면 3점, 또 다른 한 팀이 나머지 다 이기면 2점, 또 다른 한 팀이 나머지 다 이기면 1점 => 3+2+1 -> 1부터 N-1까지 더해주는 공식.
   그렇기 때문에 총 승점과 모든 팀의 승점 합이 다르다면 유효하지 않기 때문에 -1을 출력한다.

승점은 0 1 2 3 N은 4인 예제를 뒤에서부터 하나씩 보자.
첫 번째 팀은 3승을 했다. 이 말은 모든 팀과 경기에서 이겼다는 의미를 가진다. 그러면
이후 나오는 팀의 최대 승점은 2점이 된다. (3승 팀에게 졌기 때문에)
두 번째 팀은 2승을 했다. 이 말은 이후 팀들에게 다 이겼다는 의미를 가진다. 그러면
이후 나오는 팀의 최대 승점은 1점이 된다. 위 예제를 보면 각 자리에 기댓값이 존재한다.
지금부터 기댓값을 i라고 지칭하겠다.
현재 팀이 i 값이랑 같으면 아무런 처리 없이 다음 팀을 탐색한다.
현재 팀이 i 값보다 작으면 그 팀은 나오지 않은 (i - 현재 승점) 개 팀들에게는 졌다는 것을 의미한다. 그러면 가중치(W)에 (i - 현재 승점)만큼 더해준다.
현재 팀이 i 값보다 크다면 그 팀이 나온 팀 중에 i 값보다 작은 팀을 이겼다는 의미이고, 그것이 정당한지 확인하기 위해서 (i + W)보다 현재 승점이 작거나 같은지 확인한다.
작거나 같으면 유효한 승점이고 W에는 (현재 승점 - i)만큼 빼준다. 그리고 다음 탐색을 진행하고, 그렇지 않다면 유효하지 않은 승점이기 때문에 탐색을 중지하고 -1을 출력해준다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int W = 0;
    static boolean valid = true;
    static int arr[];
    static int sum = 0;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i];
        }
        if (N * (N - 1) / 2 == sum) {
            Arrays.sort(arr);
            for (int i = N - 1; i >= 0; i--) {
                if (arr[i] > i) {
                    if(arr[i] <= i + W) {
                        W -= arr[i] - i;
                    } else {
                        valid = false;
                        break;
                    }
                } else if (arr[i] < i) W += i - arr[i];
            }
            if(valid) System.out.println(1);
            else System.out.println(-1);
        } else {
            System.out.println(-1);
        }
    }
}