[백준/BOJ] platinum5 - 13560번 축구 게임 (Python)

▶13560 - 축구 게임

백준 로고

▶문제

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

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

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

 

▶입력

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

 

▶출력

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

728x90

▶풀이

일단은 시간 복잡도 생각 안 하고 막 풀었다.

퍼센트가 오르는데 생각보다 오래 걸렸지만, 시간초과가 뜨지는 않았고 통과가 되었다.

 

일단 list의 합이 얻을 수 있는 승수의 합보다 크면 -1을 출력하면 된다.

그게 아니라면 앞에서부터 계산해 주면 된다.

패배한 수를 구한 다음에, 뒤에 나오는 팀에게 1을 빼주면 된다.

(정렬을 하는 것은 필수)

무승부가 없기 때문에 간단하게 풀 수 있었다.

n = int(input())
arr = sorted(map(int, input().split()))
if sum(arr) != n * (n - 1) // 2:
    print(-1)
    exit()

for i in range(n):
    win = arr[i]
    loss = n - arr[i] - 1 - i

    for j in range(n - loss, n):
        arr[j] -= 1
        if arr[j] < 0:
            print(-1)
            exit()
        
    arr[i] = 0
    arr.sort()
    
print(1)