(BOJ) 13560 축구 게임

13560 축구 게임

• 분류 : Greedy, 탐욕 알고리즘

문제

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

Solution

Exapnder

package boj

import java.util.*

private var N: Int = 0
private lateinit var point: IntArray


fun main() {
    input()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    N = nextInt()

    point = IntArray(N) { 0 }

    for (i in 0 until N) {
        point[i] = nextInt()
    }
}

private fun solve() {
    var total = (N - 1) * N / 2
    if (total != point.sum()) {
        println(-1)
        return
    }

    point.sort()

    var sum = 0
    for (i in 0 until N) {
        sum += point[i]
        if (sum < getTotal(i)) {
            println(-1)
            return
        }
    }
    println(1)
}

private fun getTotal(number: Int): Int = number * (number + 1) / 2

Point of Thinking

• N개의 팀이 주어지면 얻을 수 있는 총점의 합은 1..N 까지의 합의 공식을 비틀어서 얻어낼 수 있다.
  • 1..N의 경우 N * (N + 1) / 2로 구할 수 있지만, 이 문제는 한 번도 못 이긴 팀이 0점을 가질 수 있다.
  • 따라서 0..N-1까지로 보고 (N - 1) * N / 2 의 값이 N개의 팀이 얻을 수 있는 총점의 합이다.
• N = 2인 경우부터 모든 경우의 수까지 꼭 받을 수 밖에 없는 점수가 있으므로 이를 위의 합계 공식으로 대조하여 없으면 -1을 반환하면 된다.
  • 단 선형적 증가가 기본이어야 하므로 입력된 값을 오름차순으로 정렬해줘야 한다.