[Algorithm] 백준 - 13560번 축구 게임 (Swift)

문제 소개

문제 풀이

사실... 이 문제는 의외로 간단하게 풀렸다. 😇

하위 팀들 조건 판별

우선 점수들을 오름차순으로 정리하고, 하위 팀들끼리 경기를 한다고 가정해보자. 하위 팀들끼리 경기를 한다고 가정한다면 최소한의 가져가야 하는 점수가 있다. 총 k개의 팀이 있다면 (k - 1) * k / 2 의 점수는 최소한 있어야 한다. 그 조건을 만족하지 않으면 -1을 출력하고 프로세스를 종료했다.

for k in 1..<n {
    if scores[...k].reduce(0, +) < k * (k - 1) / 2 {
        print(-1)
        exit(0)
    }
}

총 점수 합 판별

마지막 n개의 팀에서는 n * (n - 1) / 2 가 총합이여야 한다.

if scores.reduce(0, +) != n * (n - 1) / 2 {
    print(-1)
    exit(0)
}

이 두개의 조건을 만족해주면 주어진 점수들은 유효한 점수이다.

정답 코드

import Foundation

let n = Int(readLine()!)!
/// 1번째 팀부터 점수를 넣기 위해 (가독성을 위해) 앞에 0을 추가해줌
var scores = [0] + readLine()!.split(separator: " ").map { Int($0)! }.sorted()

for k in 1..<n {
    if scores[...k].reduce(0, +) < k * (k - 1) / 2 {
        print(-1)
        exit(0)
    }
}

if scores.reduce(0, +) != n * (n - 1) / 2 {
    print(-1)
    exit(0)
}

print(1)