[백준] 13560. 축구 게임

1. 문제 설명

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

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

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

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

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

2. 문제 접근

문제 조건 상 n개의 모든 팀은 다른 n - 1개의 팀 모두와 경기를 치뤄야 합니다.

이를 그림으로 그려보면 complete graph와 같은 형태입니다. 모든 노드가 서로 연결되어 있습니다.
각 간선은 모두 방향이 있는 간선입니다. 반드시 승 또는 패가 결정되기 때문입니다. 편의상 패에서 승으로 방향이 있다고 가정하겠습니다.

이론상 점수가 최대로 높은 팀은 점수가 n - 1점입니다. 해당 노드에 연결된 모든 간선이 그 노드로 향한다고 볼 수 있습니다. 그럼 다음으로 점수가 높은 팀은 점수가 최대 n - 2점입니다. 최소 1개의 간선은 다른 노드로 향하기 때문입니다. 이런 식으로 팀들을 점수별로 정렬하며 더했을 때 점수의 최대 limit을 구할 수 있습니다.

이걸 반대로 점수가 제일 낮은 팀부터 탐색한다 하면, 최소 점수가 0일때 다음으로 점수가 낮은 팀의 최소 점수는 1입니다. 최소 하나의 간선은 그 팀으로 간다고 보는 식으로 말이죠. 역으로 낮은 팀부터 합을 구하면 i번째 팀까지 합의 최솟값은 $i * (i - 1) / 2$입니다.

마지막으로 점수의 최종 합이 $n * (n - 1) / 2$가 맞는지만 확인해 주시면 되겠습니다.

3. 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static StringTokenizer st;

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

n = int(input())
li = list(map(int ,input().split()))
li.sort()

sum = 0
ans = 1

for i in range(n):
    sum += li[i]
    if sum < i * (i + 1) // 2: ans = -1
if sum != n * (n - 1) // 2 : ans = -1
print(ans)

자바는 역순으로, 파이썬은 정순으로 풀었습니다.