SWEA-6808:圭英と仁英のカードゲーム[Java]

17205 ワード

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

class Solution {
	// 1~18 숫자카드
	// 둘이서 9장씩 나눔
	// 9라운드 게임
	// 높은 수가 적힌 카드를 낸 사람은 두 카드에 적힌 수의 합만큼 점수
	// 낮은 수가 적힌 카드를 낸 사람은 아무런 점수도 얻을 수 없다.
	// 총점 높은 사람 이김, 같으면 무승부
	// 규영, 인영
	// 규영이가 내는 카드의 순서를 고정,
	// 인영이가 어떻게 카드를 내는지에 따른 9!가지 순서에 따라
	// 규영이가 이기는 횟수, 지는 경우
	static ArrayList<Integer> gyu, in;
	static int gwin, glose;
	static int[] numbers;
	static boolean[] isSelected;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine()); // 테스트케이스 개수

		isSelected = new boolean[9];
		numbers = new int[9];

		for (int test_case = 1; test_case <= T; test_case++) {
			in = new ArrayList<Integer>();
			for (int i = 1; i <= 18; i++) {
				in.add(i);
			}
			gyu = new ArrayList<Integer>();
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 9; i++) {
				int n = Integer.parseInt(st.nextToken());
				gyu.add(n);
				in.remove(Integer.valueOf(n));
			}
			gwin = 0;
			glose = 0;

			permutation(0);
			sb.append("#").append(test_case).append(" ").append(gwin).append(" ").append(glose).append("\n");
		}
		System.out.println(sb);

	}

	// 인영이 카드 나열하는 순열
    static void permutation(int cnt) {
        if (cnt == 9) { // 카드 아홉 개 다 나열했으면
            int gscore = 0; // 규영이 점수 합
            int iscore = 0; // 인영이 점수 합
            for (int i = 0; i < numbers.length; i++) {
                if (gyu.get(i) > numbers[i])
                    gscore += gyu.get(i) + numbers[i];
                if (gyu.get(i) < numbers[i])
                    iscore += gyu.get(i) + numbers[i];
            }
 
            // 규영이 점수와 인영이 점수 비교
            if (gscore > iscore) gwin++;
            if (gscore < iscore) glose++;
            return;
        }
        for (int i = 0; i < 9; i++) {
            if (isSelected[i]) continue;
            
            numbers[cnt] = in.get(i);
            isSelected[i] = true;
 
            permutation(cnt + 1);
            isSelected[i] = false;
        }
    }
}