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

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AW2Jldrqlo4DFASu&categoryId=AW2Jldrqlo4DFASu&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=2

SW Expert Academy

 

풀이

2^k 명의 사람이 출전하여 2명씩 차례로 경기를 하게 되어 그 다음은 2^k-1 번 경기를 하고 그 다음은 2^k-2 번 경기를 하고 ,,, 이렇게 되면 마지막에 최종 1명이 남게 된다.

 

필자는 재귀 방식을 활용하였다. (떠오른 방식이 이 방식 밖에 없었다..)

처음 입력 받은 2^k 명의 사람들과 지루함의 값을 계산할 sum을 매개변수로 넣어준다. sum은 경기를 시작할 때는 0

 

game이라는 메서드에는 다음 라운드를 진행할 사람들을 추려야 하기 때문에 리스트를 선언해주었고 라운드에 해당하는 매개변수로 받은 리스트에서 2명의 차이를 지루함 값에 더해주고 값이 더 큰 (코딩 실력이 더 좋은) 사람이 다음 라운드 리스트에 담기게 되고 다음 라운드인 game()을 호출한다.

 

라운드의 사람이 1명이 남게될 때까지 진행되고 마지막 승자가 결정되면 지금까지 더한 지루함 값을 출력하는 방식으로 구현하였다.

 

전체 코드

package com.swea.D3.p8673;

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            sb.append("#" + t + " ");

            int N = Integer.parseInt(br.readLine());

            StringTokenizer st = new StringTokenizer(br.readLine());
            List<Integer> list = new ArrayList<>();

            for (int i = 0; i < (int) Math.pow(2, N); i++) {
                list.add(Integer.parseInt(st.nextToken()));
            }

            sb.append(game(list, 0) + "\n");
        }

        System.out.println(sb);
    }

    static int game(List<Integer> round, int sum) {
        List<Integer> nextRound = new ArrayList<>();

        if (round.size() == 1) {
            return sum;
        }

        int size = round.size();
        for (int i = 0; i < size - 1; i += 2) {
            sum += Math.abs(round.get(i) - round.get(i + 1));
            nextRound.add(Math.max(round.get(i), round.get(i + 1)));
        }

        return game(nextRound, sum);
    }
}