8673. 코딩 토너먼트1 D3

요즘 알바 갔다가 헬스하고 집에 돌아오면 너무 피곤해서 그대로 뻗어버려가지고 며칠 동안 게을러져서 안썼다.

어제 하루 푹쉬니까 컨디션 좋아졌고 오늘 여러문제 풀어본다

일단 첫 문제는 머리 풀기 위해 워밍업 문제로 정답률이 무려 75%!!

문제부터 보자

2K명의 사람이 코딩 토너먼트에 출전한다.
이 토너먼트는 싱글 엘리미네이션(single-elimination)방식으로,
각 사람은 최대 K번의 경기를 펼치게 된다.
다음과 같은 그림의 대진표가 나오는 방식이다.



           

정확하게 하면, 사람들에게 1에서 2K까지의 번호를 붙였을 때 토너먼트는 다음과 같은 방식으로 진행된다.

1. 1라운드는 1번과 2번, 3번과 4번, … , 2K-1번과 2K번이 서로 코딩 대결을 펼친다.
   총 2K-1번의 경기가 펼쳐지며, 각 경기의 승자를 W1,1, W1,2, … , W1,2K-1라고 하자.
2. 2라운드는 W1,1과 W1,2, W1,3과 W1,4, … , W1,2K-1-1과 W1,2K-1이 서로 코딩 대결을 펼친다.
   총 WK-2번의 경기가 펼쳐지며, 각 경기의 승자를 W2,1, W2,2, … , W2,2K-2라고 하자.

…

K. K라운드는 WK-1,1과 WK-1,2가 서로 코딩 대결을 펼친다.
   총 한 번의 경기가 펼쳐지며, 최종 승자가 결정된다.

진수는 모든 사람의 코딩 실력을 파악하고 있는데, 두 사람이 코딩 대결을 하면 코딩 실력이 높은 사람이 반드시 승자가 된다.
만약 두 사람의 코딩 실력이 같으면 둘 중 한 명이 이긴다.
대진표가 이미 정해져 있으므로 이미 결과는 정해져 있다.
2K명의 사람이 있으므로, 총 2K-1번의 경기가 펼쳐지고, 모든 경기는 사람들에게 중계된다.
진수는 모든 경기를 보면 사람들이 얼마나 지루해 할 것인지 알아보고 싶다.
실력이 차이가 나면 날수록 경기가 지루하기 때문에, 어떤 대결의 지루한 정도는 경기를 하는 두 사람의 코딩 실력의 차이와 같다.
진수를 도와 모든 경기에 대해 경기의 지루한 정도의 총합을 구하는 프로그램을 작성하라.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 정수 K(1 ≤ K ≤ 10)이 주어진다.
두 번째 줄에는 2K개의 정수 A1, A2, … , A2K(1 ≤ Ai ≤ 105)이 공백 하나로 구분되어 주어진다.
Ai는 i번 사람의 코딩 실력을 나타낸다.

[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
각 테스트 케이스 마다 모든 경기의 지루한 정도의 총합을 출력한다.

문제는 이렇다. 토너먼트를 진행하는데 각 승부시 차이 만큼을 모두 더해 출력하라는 의미다.

처음에는 배열로 할까 고민했는데 queue를 이용하면 아주 간편하게 할 수 있을 것 같아 queue를 이용했다.

문제 푸는 방식은

1.입력을 받아 모두 queue에 푸시

2. queue의 앞에 두개를 뽑아 차이 만큼을 answer에 더하고 둘 중에 큰걸 다시 push

3. 2번 계속 반복

4. 2번을 반복하다 보면 마지막 1개만 남을 수 있는데 그래서 while문 중간에 queue가 비면 break

코드

#include <iostream>
#include <queue>
#include <math.h>
using namespace std;
 
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int TC,N,temp,ans;
    cin>>TC;
    for (int t=1;t<=TC;t++)
    {
        cin>>N;
        ans = 0;
        queue<int> MAP;
        for(int i=0;i<pow(2,N);i++)
        {
            cin>>temp;
            MAP.push(temp);
        }
        while(!MAP.empty())
        {
            int temp1, temp2;
            temp1 = MAP.front();
            MAP.pop();
            if(MAP.empty()){
                break;
            }
            temp2 = MAP.front();
            MAP.pop();
            ans+=(max(temp1, temp2)-min(temp1, temp2));
            MAP.push(max(temp1,temp2));
        }
        cout<<"#"<<t<<' '<<ans<<'\n';
    }
    return 0;
}