/ SWEA

SWEA_6808_규영이와인영이의카드게임_JAVA

문제 : 규영이와인영이의카드게임

SWEA문제는 로그인을 해야 열람할 수 있습니다.

링크 : SWEA_6808_규영이와인영이의카드게임

접근 방식

순열문제인데, 18개의 숫자중 9개씩 2명이 나눠갖는 방법을 찾는데 고민을 많이 했다. 배열에 카운트하는 방식으로 간단하게 할 수 있는 모양이지만, 이 문제를 풀 당시 나는 그에 대한 생각을 하지 못해서 다른 방법으로 구분을 지었다. A와 B에게 카드를 나눠준다고 할때, 각각 list로 값을 읽어들인다. A에게 나눠주는 카드는 주어져 있으므로, 1~18까지 반복하면서 contains를 이용하여 A에게 없는 카드이면서 B에게도 없는 카드를 B에게 add시켜주도록 한다.

값을 서로 나누고 나면, B가 가진 카드의 배치에 대한 경우의 수를 모두 구해서 A의 배열을 기준으로 비교를 해주면 된다. A가 승리시 카운트를 증가시켜, A가 이기는 경우의 수를 출력하고, 모든 경우의 수가 9!라고 하였으니 9!에서 A가 이기는 경우의 수를 빼주면 A가 지는 경우의 수를 알 수 있다.

풀이 방법

  1. 리스트 2개를 생성한다.

  2. 먼저 리스트 1개에 A에게 주어진 수를 읽어들여 모두 추가한다.

  3. 1~18까지 반복하며, A에게 없으면서 B에게 없는 수를 B의 리스트에 추가한다.

  4. 재귀함수를 통해 순열을 구현하여, B가 가질수 있는 카드의 배치의 경우를 모두 구한다.

  5. 재귀함수의 기저조건에서, 각 배치별로 A가 가진 카드의 배열과 비교하여, 승리하는 상황에 카운트를 1 증가시킨다.

  6. 모든 순열에 대한 비교를 마친 후 승리하는 경우의 수와 패배하는 경우의 수를 공백을 기준으로 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class D3_6808_규영이와인영이의카드게임 {
	static List<Integer> card1;
	static List<Integer> card2;
	static int[] nums;
	static boolean[] isSelected;
	static int win;
	public static void main(String[] args) throws IOException {

		System.setIn(new FileInputStream("input_6808.txt"));


		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		// 순열의 문제
		// 1 ~ 18까지

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


		for(int tc=1;tc<=T;tc++) {
			card1 = new ArrayList<>();
			card2 = new ArrayList<>();
			win = 0;
			StringTokenizer st = new StringTokenizer(in.readLine()," ");
			isSelected = new boolean[9];
			nums = new int[9];
			for(int i=0;i<9;i++) {
				card1.add(Integer.parseInt(st.nextToken()));
			}

			for(int i=0;i<9;i++) {
				for(int j=1;j<=18;j++) {
					if(!card1.contains(j) && !card2.contains(j)) {
						card2.add(j);
						break;
					}
				}
			}

			perm(0);
			System.out.printf("#%d %d %d\n",tc,win,(362880-win));
		}


	}


	public static void perm(int cnt) {

		if(cnt == 9) {
			int winA = 0;
			int winB = 0;
			for(int i=0;i<9;i++) {
				int A = card1.get(i);
				int B = nums[i];
				if(A > B) {
					winA = winA + A + B;
				}else if(A<B){
					winB = winB + A + B;
				}
			}
			if(winA > winB) {
				win++;
			}
			return;
		}

		for(int i=0;i<9;i++) {
			if(isSelected[i]) {
				continue;
			}
			isSelected[i] = true;
			nums[cnt] = card2.get(i);
			perm(cnt + 1);
			isSelected[i] = false;

		}


	}

}