6808번. 규영이와인영이의카드게임

규영이와 인영이는 1에서 18까지의 수가 적힌 18장의 카드로 게임을 하고 있다.

한 번의 게임에 둘은 카드를 잘 섞어 9장씩 카드를 나눈다. 그리고 아홉 라운드에 걸쳐 게임을 진행한다.

한 라운드에는 한 장씩 카드를 낸 다음 두 사람이 낸 카드에 적힌 수를 비교해서 점수를 계산한다.

높은 수가 적힌 카드를 낸 사람은 두 카드에 적힌 수의 합만큼 점수를 얻고,

낮은 수가 적힌 카드를 낸 사람은 아무런 점수도 얻을 수 없다.

이렇게 아홉 라운드를 끝내고 총점을 따졌을 때, 총점이 더 높은 사람이 이 게임의 승자가 된다.

두 사람의 총점이 같으면 무승부이다.

이번 게임에 규영이가 받은 9장의 카드에 적힌 수가 주어진다.

규영이가 내는 카드의 순서를 고정하면, 인영이가 어떻게 카드를 내는지에 따른 9!가지 순서에 따라

규영이의 승패가 정해질 것이다.

이 때, 규영이가 이기는 경우와 지는 경우가 총 몇 가지 인지 구하는 프로그램을 작성하라.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 아홉 개의 정수가 공백으로 구분되어 주어진다.

각 정수는 1이상 18이하이며, 같은 정수는 없다.

규영이는 정수가 주어지는 순서대로 카드를 낸다고 생각하면 된다.


[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고 한 칸을 띄운 후,

인영이가 카드를 내는 9! 가지의 경우에 대해 규영이가 게임을 이기는 경우의 수와 게임을 지는 경우의 수를

공백 하나로 구분하여 출력한다.

입력

4 1 3 5 7 9 11 13 15 17 18 16 14 12 10 8 6 4 2 13 17 9 5 18 7 11 1 15 1 6 7 9 12 13 15 17 18

//테스트 케이스 개수 //1st TC, 9장의 카드에 대한 정보         //2nd TC

출력

#1 112097 250783 #2 250783 112097 #3 336560 26320 #4 346656 16224

//첫 번째 테스트케이스 결과 //두 번째 테스트케이스 결과

package a0812;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Solution_규영이와인영이의카드게임_서울_12반_이서영 {

	static int[] gy ;
	static int[] iy ;
	static int[] chk;
	static int wincnt =0;
	static int losecnt =0;

	// 9개수 나열을 모두 다르게 해서 이긴횟수 진횟수 구하기 -> 순열을 이용한다.
	public static void findWinCount(ArrayList<Integer>a,int[] iychk){
		
		if(a.size()==9) {
			int gys =0;
			int iys = 0;
			for(int i=0; i<9; i++) {
				if(gy[i]>a.get(i)) {
					gys=gys+gy[i]+a.get(i);
				}
				else {
					iys=iys+gy[i]+a.get(i);
				}
			}
			if(gys>iys) {
				
				wincnt++;
			}
			else if(gys<iys) {
				losecnt++;
			}
			return;
		}
		
		for(int i=0; i<iy.length; i++) {
			
			if(iychk[i]==0) { //주의!!! a.contains(iy[i])하면 시간 오래걸림 
				iychk[i]=1;
				a.add(iy[i]);
				findWinCount(a,iychk);
				a.remove(a.size()-1);
				iychk[i]=0;
			}
			
			
		}
		
		
		
	}
	
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("res/6806_input.txt")));
		int T;
		T=Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st; 
		for(int tc = 1; tc <= T; tc++)
		{
			gy = new int[9];
			iy = new int [9];
			chk = new int[19];
			 st = new StringTokenizer(br.readLine());
			for(int i=0;i<9; i++) {
				gy[i] = Integer.parseInt(st.nextToken());
				chk[gy[i]]=1;
				
			}
			int idx =0;
			for(int i=1;i<=18; i++) {
				if(chk[i]==0 && idx<9) {
					iy[idx]=i;
					idx++;
				}
			}
			wincnt =0;
			losecnt=0;
			findWinCount(new ArrayList<Integer>(), new int[9]);
		
			sb.append("#").append(tc+" "+wincnt+" "+losecnt+"\n");
		}
		
	System.out.println(sb);
	}	
}

- 순열을 이용해서 푸는 문제

- a.contains() 를 쓰게되면 시간 소요가 많이 되므로 왠만하면 check배열을 쓰자.