[SWEA]코딩_토너먼트1

Posted on | In |

문제 보러가기

제한사항

두 번째 줄에는 2K개의 정수 A1, A2, … , A2K(1 ≤ Ai ≤ 105)이 공백 하나로 구분되어 주어진다.

첫번째 생각

두 숫자의 차이를 모두 더하면 된다. 대진표는 Queue로 관리를 한다.

1
int Size = q.size();

로 관리를 하면 토너먼트의 16강, 8강, 4강과 같이 한 시점을 나눠서 계산할 수 있을 것이다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
	static Scanner sc;
	static Queue<Integer> q;
	static int sum;
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1;tc<=T;tc++) {
			
			init();
			run();
			System.out.println("#"+tc+" "+sum);
		}

	}
	public static void init() {
		int K = sc.nextInt();
		int S = (int)Math.pow(2, K);
		sum = 0;
		q = new LinkedList<>();
		for(int i=0; i<S; i++) {
			q.add(sc.nextInt());
		}
	}
	
	public static void run() {
		while(q.size() > 1) { // 혼자 남는다면 토너먼트의 승리자
			int size = q.size(); 
			for(int i=0; i<size/2; i++) {
				int A = q.poll();
				int B = q.poll();
				sum += Math.abs(A-B);
				int tmp = A > B ? A : B; // 승리자는 다시 큐에 들어간다.
				q.add(tmp);
			}
		}
	}
}