[JAVA] 축구 게임_13560

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

13560번: 축구 게임

 

 

 

축구 게임 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

3852

791

597

25.264%

문제

축구는 지구에서 가장 인기있는 스포츠 중의 하나입니다. 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

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2016 B번

• 데이터를 추가한 사람: deneb2016, WeissBlume
• 문제를 번역한 사람: sgchoi5
• 잘못된 데이터를 찾은 사람: shjgkwo

알고리즘 분류

• 수학
• 그리디 알고리즘

 

---

import java.util.Scanner;
import java.util.Arrays;

public class Main
{
    private static Scanner s = new Scanner(System.in);
    
    private static int CORRECT = 1;
    private static int INCORRECT = -1;
    
    public static void main(String[] args) {
    	
    	int n = s.nextInt(); // 팀의 수
    	int[] scores = new int[n]; // 각 팀의 승점
    	
    	int maxGames = (n-1)*n / 2; // 경기수에 따라 나올 수 있는 최대 승점
    	int sum = 0;
    	Boolean hasAllGameWinner1 = false; // 모든 경기를 이긴 팀이 존재하는가?
    	Boolean hasAllGameWinner2 = false; // 모든 경기를 이긴 팀이 또 존재하는가?
    	Boolean hasAllGameLooser = false; // 모든 경기를 진 팀이 존재하는가?
    	
    	for(int i=0; i<n; i++) {
    		scores[i] = s.nextInt();
    		sum += scores[i];
    		
    		if(scores[i] == (n-1)) {
    			if(!hasAllGameWinner1) {
    				hasAllGameWinner1 = true;
    			}
    			else {
    				hasAllGameWinner2 = true;
    			}
    		}
    		
    		if(scores[i] == 0) {
    			hasAllGameLooser = true;
    		}
    	}
    	
    	// 총 경기 수보다 작거나 크면 -1
    	if(maxGames > sum || maxGames < sum) {
    		System.out.println(INCORRECT);
    	}
    	
    	// 전승팀이 두 팀이상 존재
    	else if(hasAllGameWinner2) {
    		System.out.println(INCORRECT);
    	}
    	
    	// 전승팀이 존재하는데 전패팀이 존재하지 않음
    	else if(hasAllGameWinner1 && !hasAllGameLooser) {
    		System.out.println(INCORRECT);
    	}
    	
    	//모든 경우를 통과했으면
    	else {
    		
    		// 랑주의 정리 : S[i] 까지의 합은 nC2 보다 낮을 수 없다.
    		Arrays.sort(scores);
    		
    		sum = 0;
    		for(int i=0; i<n; i++) {
    			sum += scores[i];
    			if(sum < (i+1)*i/2 ) {
    				System.out.println(INCORRECT);
    				return;
    			}
    		}
    		
    		// 랑주의 정리도 통과했으면 1
    		System.out.println(CORRECT);
    	}
    }
}