[백준 02262] 토너먼트 만들기 [Java]

문제

http://boj.ma/2262

요약

• 토너먼트 결승전까지 각 두 선수의 랭킹 차이의 총 합 최소를 구하자.
• 초기에 주어진 선수의 순서는 불변하고, 대진표가 교차되지 않도록 구상해야 한다.

---

풀이 과정

아이디어

초기 선수의 순서가 불변하고, 대진표가 교차되지 않으면서도 랭킹 차이의 총 합을 최소로 해야한다.

경기가 진행됨에 따라 높은 순위(1에 가까운)들만 남게 되며, 낮은 순위의 선수들이 조기에 탈락(?)되어야 랭킹 차이의 총 합이 최소가 된다.

순위가 N위인 선수부터, 2위인 선수들이 문제의 조건을 준수하며 랭킹 차이가 최소가 되도록 대진표를 구성하면 된다.

// Solve
int sum = 0;
for (int rank = N; rank >= 2; --rank) {
    int lastRankIdx = R.indexOf(rank);

    int minDiff = Integer.MAX_VALUE;
    if (lastRankIdx > 0) {
        minDiff = Math.min(Math.abs(R.get(lastRankIdx - 1) - rank), minDiff);
    }
    if (lastRankIdx < R.size() - 1) {
        minDiff = Math.min(Math.abs(R.get(lastRankIdx + 1) - rank), minDiff);
    }

    sum += minDiff;
    R.remove(lastRankIdx);
}

시간복잡도는 $O(N^2)$이지만 N은 최대 256으로 ≤ 2s 이내에 충분히 통과된다.

성능 분석

• 시간 복잡도: $O(N^2)$
• 제출결과: Accepted / 140ms / 14,144KB

---

회고

처음에는 두 선수의 랭킹 차이가 큰 경기부터 진행하는 방법을 떠올렸으나, 이는 한 선수가 다른 선수들보다 랭킹이 높을 때 최적해가 아니게 된다.

전체 대진표에서 임의의 두 선수 랭킹보다 낮은 랭킹의 선수가 있으면 최적해가 보장이 되지 않으므로 랭킹이 낮은 선수부터 탈락시켜야 한다.

순수 Greedy 유형의 문제라 한 번 풀면 이해는 되지만 처음부터 풀이를 떠올리기 어려웠던 것 같다.

---

참고

문제

http://boj.ma/2262

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/02262.java