백준 2262번: 토너먼트 만들기 (Kotlin)

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

2262번: 토너먼트 만들기

안녕하세요, 이륙사입니다. 이번 게시물에서는 토너먼트 만들기 문제를 풀고 개인적으로 되돌아본 점을 기록했습니다.

 

핵심 아이디어

랭킹이 낮은(값이 큰) 선수들이 오래 남아 있을수록 랭킹 차의 합이 커진다.

왜냐면 토너먼트를 진행할수록 랭킹 값이 작은 선수들이 올라오기 때문에, 랭킹 값이 큰 선수들이 부전승으로 올라가면 항상 처음에 옆에 있던 선수들보다 랭킹 값이 같거나 작은 선수들과 맞붙게 된다.

 

ex) 1 4 2 5 3 7 - 랭킹차가 가장 작은 선수들부터 시합을 할 경우,

1 4 2 3 7 -> 1 4 2 7  -> 1 2 7 -> 1 2 -> 1 

만약 처음에 7과 3이 대결했다면 7에 의한 랭킹 차는 4로 끝났을 것이다.

 

따라서, 랭킹이 낮은 선수부터 우선적으로 게임을 진행시켜 떨어뜨린다.

 

회고

처음에 매 반복마다 랭킹 차가 작은 선수들부터 대결시키면 되겠구나 생각해서 틀렸다. 이후에 1 2 3 4 5 6 예시를 떠올리면서 랭킹차가 작은 선수들 중에서 값이 큰 선수들부터 대결시키면 되겠다 싶었는데, 그것도 아니었다.

사실 어떻게 위 아이디어를 떠올릴 수 있었을지 아직 잘 모르겠다.

 

랭킹 차이 합의 최소를 구한다 -> 위로 올라갈수록 랭킹이 높은 선수들이 남는다 -> 그들과 나중에 맞붙지 않도록 랭킹이 낮은 선수들을 먼저 떨어뜨린다.

 

이렇게 떠올릴 수 있었을까?

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.abs
import kotlin.math.min

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())
    val rankings = MutableList(n) {
        st.nextToken().toInt()
    }

    print(getMinDiffSum(rankings))
}

fun getMinDiffSum(rankings: MutableList<Int>): Int {
    var sumOfDiff = 0 // 정답

    while (rankings.size > 1) {
        var maxRankIndex = 0

        // 랭킹이 가장 낮은(값이 큰) 선수를 찾는다
        for (i in 0 until rankings.size) {
            if (rankings[i] == rankings.size) {
                maxRankIndex = i
                break
            }
        }

        // 랭킹 차이가 더 작은 선수와 대결한다
        sumOfDiff += when {
            maxRankIndex == 0 -> abs(rankings[maxRankIndex] - rankings[maxRankIndex + 1])
            maxRankIndex == rankings.lastIndex -> abs(rankings[maxRankIndex] - rankings[maxRankIndex - 1])
            else -> min(
                abs(rankings[maxRankIndex] - rankings[maxRankIndex + 1]),
                abs(rankings[maxRankIndex] - rankings[maxRankIndex - 1])
            )
        }

        rankings.removeAt(maxRankIndex)
    }

    return sumOfDiff
}