[Java] SW6808: 규영이와 인영이의 카드게임

• 시간 : 100개 테스트케이스를 합쳐서 C의 경우 3초 / C++의 경우 3초 / Java의 경우 6초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


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

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

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

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

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

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

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

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

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

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

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


[입력]

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

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

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

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


[출력]

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

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

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

 

[풀이]

총 18카드를 반으로 나눈 다음 9장씩 배분합니다.

승리 방식이 독특한데 더 큰 숫자를 낸 사람이 이기고 이긴 사람이 양쪽 숫자의 합을 점수로 가져가는 방식입니다.

 

규영이의 카드 입력 받기

규영이의 카드를 입력 받으면서 정수 배열에 카드 값들을 기록해주고

카운팅 배열을 만들어 규영이가 입력받은 카드들을 모두 체크해줍니다.

    for(int i=0; i<9; i++) { //규영이 덱 만들기
        G[i] = Integer.parseInt(st.nextToken());
        count[G[i]] = true;
    }

 

인영이 카드 목록 만들기

카운팅 배열에 체크되지 않은 카드는 모두 인영이의 것입니다. 그 숫자들을 모두 인영이의 덱으로 불러옵니다.

int idx = 0; //인덱스에 맞춰넣기 위해 변수 지정

for(int i=1; i<19; i++) { // 인영이 덱 완성
    if(!count[i]) { // 카운트에 체크가 없다면
        I[idx] = i; // 인영덱에 넣고
        idx++; // 인덱스 조정
}

 

순열만들기

dfs를 이용해 순열을 구현합니다.

방문체크 배열을 만듭니다.(static)

새로운 순서로 나열된 카드를 기록하기 위한 배열도 만듭니다.

static int[] answer = new int[9];  //인영이 덱 순서 나열
static int[] visit = new boolean[9];

 

dfs를 만들고 1번째에서 9번째 카드 중 하나를 선택하고 그 카드의 값을 기록한다음 방문체크합니다.

원하는 깊이에 도달하면 지금까지 기록한 순서의 카드를 규영이의 카드와 비교한다음 누가 이겼는지 확인합니다.

static void dfs(int depth) {
		if(depth==-1) {
			int sumG = 0;
			int sumI = 0;
			
			for(int i=0; i<9; i++) {
				if(answer[i]>G[i]) {
					sumI += answer[i]+G[i];
				}else if(answer[i]<G[i]) {
					sumG += answer[i]+G[i];
				}
			}
			
			if(sumI > sumG) {
				lose++;
			}else if(sumI < sumG) {
				win++;
			}
			return;
		}
		
		for(int i=0; i<9; i++) {
			if(!visit[i]) { //방문하지 않았을 때
				visit[i] = true;
				answer[depth] = I[i];
				dfs(depth-1);
				visit[i] = false;
			}
		}
	}

 

전체코드

import java.util.*;
import java.io.*;
 
public class Solution {
	static boolean[] visit;
	static int[] answer = new int[9];  //인영이 덱 순서 나열
	static int[] G,I;
	static int lose,win;
	
	static void dfs(int depth) {
		if(depth==-1) {
			int sumG = 0;
			int sumI = 0;
			
			for(int i=0; i<9; i++) {
				if(answer[i]>G[i]) {
					sumI += answer[i]+G[i];
				}else if(answer[i]<G[i]) {
					sumG += answer[i]+G[i];
				}
			}
			
			if(sumI > sumG) {
				lose++;
			}else if(sumI < sumG) {
				win++;
			}
			return;
		}
		
		for(int i=0; i<9; i++) {
			if(!visit[i]) { //방문하지 않았을 때
				visit[i] = true;
				answer[depth] = I[i];
				dfs(depth-1);
				visit[i] = false;
			}
		}
	}
    public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int T = Integer.parseInt(br.readLine());
    G = new int[9]; // 규영이 덱 
    I = new int[9]; // 인영이 덱
    
    for(int t = 1; t<=T; t++) {
    	st = new StringTokenizer(br.readLine());
    	
    	boolean[] count = new boolean[19]; // 카운트
    	
    	for(int i=0; i<9; i++) { //규영이 덱 만들기
    		G[i] = Integer.parseInt(st.nextToken());
    		count[G[i]] = true;
    	}
    	int idx = 0;
    	for(int i=1; i<19; i++) { // 인영이 덱 완성
    		if(!count[i]) {
    			I[idx] = i;
    			idx++;
    		}
    	}
    	
    	lose = 0; //패배 승리 경우의 수 카운트
    	win = 0;
    	
    	visit = new boolean[9];
    	
    	dfs(8);
    	System.out.println("#"+t+" "+win+" "+lose);
    }
    	
}
}