[SWEA] 8673. 코딩 토너먼트1

문제 링크

[SWEA] 8673. 코딩 토너먼트1

풀이 과정

int K = sc.nextInt();
int[] players = new int[1 << K];
int answer = 0;

for (int i = 0; i < 1 << K; i++) players[i] = sc.nextInt();

먼저, 토너먼트에 참가하는 참가자 수는 $2^K$명이므로, 참가자 수에 맞는 크기의 player 배열을 선업합니다. 이후, 토너먼트에 참가하는 사람들의 코딩 실력을 입력받습니다.

while (K > 0) {
    int[] survived = new int[1 << (K - 1)];

    for (int i = 0; i < 1 << K; i += 2) {
        survived[i / 2] = Math.max(players[i], players[i + 1]);
        answer += Math.abs(players[i] - players[i + 1]);
    }

    players = survived;
    K--;
}

살아남은 사람은 K/2 명입니다. 살아남은 사람의 코딩 실력을 저장하기 위해 survived 배열을 선업합니다. 이후, 인접한 두 명의 코딩 실력을 비교해, 살릴 사람의 코딩 실력을 survived 에 저장한 후, 둘의 차이를 변수 answer 에 누적시킵니다. 위 과정을 1명이 남을 때까지 반복합니다.

코드

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int TC = sc.nextInt();

        for (int tc = 1; tc <= TC; tc++) {
            int K = sc.nextInt();
            int[] players = new int[1 << K];
            int answer = 0;

            for (int i = 0; i < 1 << K; i++) players[i] = sc.nextInt();

            while (K > 0) {
                int[] survived = new int[1 << (K - 1)];

                for (int i = 0; i < 1 << K; i += 2) {
                    survived[i / 2] = Math.max(players[i], players[i + 1]);
                    answer += Math.abs(players[i] - players[i + 1]);
                }

                players = survived;
                K--;
            }

            System.out.println("#" + tc + " " + answer);
        }
    }
}