[백준] 13560번. 축구 게임(JAVA)

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

---

문제

---

풀이

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        Integer[] arr = new Integer[n];

        int sum = 0;

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i];
        }

        Arrays.sort(arr);

        int result = 1;

        if(sum != (n-1) * n / 2){ // 합계 점수가 안 맞을 때
            result = -1;
        } else{
            int cnt = 0;
            for(int i = 0; i < n; i++){
                cnt += arr[i];
                if(cnt < (i+1) * i /2){
                    result = -1;
                }
            }
        }

        System.out.println(result);

    }

}

 

문제를 이해하는 것이 중요한 문제이다. 먼저 축구 게임이라는 룰을 이해하면 시작 플레이어는 최대 n-1의 점수를 가질 수 있고, 모든 팀의 승점 합은 (n-1)*n/2가 되어야 한다.

 

제일 강한 팀부터 생각해보자. 첫 팀은 최대 n-1의 승점을 가져갈 수 있다. 다음 팀은 n-2점까지의 승점을 가져갈 수 있게 된다.(가장 강한 팀에게는 져야 하기 때문이다.) 즉, 위의 팀부터 n-1, n-2,... 의 승점을 가져갈 수 있는 것이 최댓값이라는 소리이다.

 

그렇기 때문에 약팀을 기준으로 한다면 그 반대인

cnt < (i+1) * i /2

의 조건을 만족시켜야 성립하게 되는 문제이다.

 

추가적으로 우선순위 큐 위주의 문제를 풀면서 13560번이 있길래 풀었는데 우선순위 큐보다는 그리디 혹은 수학 문제에 가깝다고 생각된다. 우선순위 큐는 동일한 수를 저장할 수 없기 때문이다. (이 점을 다시 한번 상기시키고 가야할 것 같다.)