문제

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

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

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

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

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

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

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

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

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

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

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

문제 접근

완전탐색으로 인영이가 낼 수 있는 모든 카드 순열을 구하고 각 라운드의 점수를 계산하면 된다.

순열 만들기 : DFS

	//DFS로 순열 만들기
	private static void perm(int depth, int[] pick) {
    	//종료조건
		if (depth == 9) {
        	//점수 계산하는 메서드로 이동
			play(pick);
			return;
            
		for (int i = 0; i < 9; i++) {
			if (!visited[i]) {
				visited[i]  = true;
				pick[depth] = iCard[i];
				perm(depth + 1, pick);
				visited[i] = false;
			}
		}
		
	}

순열 만들기 : 비트마스킹

	//비트마스킹으로 순열 구하기
	
	private static void perm(int depth, int mask, int[] pick) {
	    if (depth == 9) {
	        play(pick);
	        return;
	    }

	    for (int i = 0; i < 9; i++) {
	    	 // 아직 안 뽑은 카드라면 (!visited[i])와 같은 의
	    	// (1 << i)는 i번째만 1인 
	        if ((mask & (1 << i)) == 0) {
	            pick[depth] = iCard[i];
	            //mask | (1 <<i) 는 i번째는 썼다고 표시하는 것 (visited[i] = true 와 같은 의)
	            perm(depth + 1, mask | (1 << i), pick); 
	            //비트마스킹은 방문배열 false로 다시 되돌릴 필요가 없다. 원래의 mask는 변하지 않고 유지되기 때문에 
	        }
	    }
	}

전체 코드

package swea;

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

public class cardGame {
	static int[] gCard;
	static int[] iCard;
	static boolean[] visited;
	
	static int winCount;
	static int loseCount;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		System.setIn(new FileInputStream("src/input.txt"));

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

		int T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; tc++) {
			winCount = 0;
			loseCount = 0;
			
			gCard = new int[9];
			iCard = new int[9];
			
			visited = new boolean[9];
			
			List<Integer> list = new ArrayList<>();
			for (int i = 1 ; i <= 18; i++) {
				list.add(i);
			}
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for (int i = 0; i < 9; i++) {
				gCard[i] = Integer.parseInt( st.nextToken());
				list.remove(Integer.valueOf(gCard[i])); //인덱스가 아닌 값으로 삭제하는 방법 
			}
			
			//인영이 카드 저장
			for (int i = 0; i < 9; i++) {
				iCard[i] = list.get(i);
			}
			
			//순열
			perm(0, new int[9]);

			System.out.println("#" + tc + " " + winCount + " " + loseCount);
			
			
		}
	}

	//DFS로 순
	private static void perm(int depth, int[] pick) {
		if (depth == 9) {
			play(pick);
			return;
		}
		
		for (int i = 0; i < 9; i++) {
			if (!visited[i]) {
				visited[i]  = true;
				pick[depth] = iCard[i];
				perm(depth + 1, pick);
				visited[i] = false;
			}
		}
		
	}
	
    //점수 계산하는 과정
	static void play(int[] iCard2) {
		int gScore = 0, iScore = 0;
		for (int i = 0; i < 9; i++){
			if (gCard[i] > iCard2[i] ) {
				gScore += gCard[i] + iCard2[i];
			}
			else {
				iScore += gCard[i] + iCard2[i];
			}
		}
		
		if (gScore > iScore) {
			winCount += 1;
		} else {
			loseCount += 1;
		}
		
	}
}