SWEA 6808 - 규영이와 인영이의 카드게임

Java

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

문제

규영이와 인영이는 1에서 18까지의 수가 적힌 18장의 카드로 게임을 하고 있다.
한 번의 게임에 둘은 카드를 잘 섞어 9장씩 카드를 나눈다. 그리고 아홉 라운드에 걸쳐 게임을 진행한다.
한 라운드에는 한 장씩 카드를 낸 다음 두 사람이 낸 카드에 적힌 수를 비교해서 점수를 계산한다.
높은 수가 적힌 카드를 낸 사람은 두 카드에 적힌 수의 합만큼 점수를 얻고,
낮은 수가 적힌 카드를 낸 사람은 아무런 점수도 얻을 수 없다.
이렇게 아홉 라운드를 끝내고 총점을 따졌을 때, 총점이 더 높은 사람이 이 게임의 승자가 된다.
두 사람의 총점이 같으면 무승부이다.
이번 게임에 규영이가 받은 9장의 카드에 적힌 수가 주어진다.
규영이가 내는 카드의 순서를 고정하면, 인영이가 어떻게 카드를 내는지에 따른 9!가지 순서에 따라
규영이의 승패가 정해질 것이다.
이 때, 규영이가 이기는 경우와 지는 경우가 총 몇 가지 인지 구하는 프로그램을 작성하라.

접근 방법

규영의 카드를 기준으로 인영이의 카드도 초기화 한다.
인영이가 내는 카드 순서를 순열을 통해 바꾼뒤 규영이와 9장을 비교하여 점수를 계산한다.
총 인영이의 카드 순서는 9! 만큼의 경우의 수가 주어진다.

구현

우선 인덱스 1 ~ 18 까지 담을 수 있는 전체 카드 배열을 초기화한다.
규영이의 카드를 저장 할 때마다, 위 전체 카드 배열 인덱스에 규영이의 카드 위치를 배정하여 규영이의 카드 위치를 나타낸다.
전체 카드 배열에서 뽑히지 않은 카드를 인영이의 카드로 선언한다.

DFS를 통해 인영이의 9장의 카드 순열을 구현한다.
9장의 카드가 뽑혔을 때, 인영이와 규영이의 카드를 한장 씩 비교하여 더 큰 사람에게 카드의 합 점수를 부여한다.
최종 점수를 비교하여 승패를 결정한다.

코드

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

class Solution {
	static int win = 0, lose = 0, draw = 0;
	static int[] a, b, ab;
	static int[] sel, vsi;
	public static void main(String []args) throws Exception {  
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	int tc = stoi(br.readLine());
    	for(int idx = 1; idx <= tc; idx++) {
    		st = new StringTokenizer(br.readLine());
    		a = new int[9];
    		b = new int[9];
    		ab = new int[19];
    		sel = new int[9];
    		vsi = new int[9];
    		win = 0;
    		lose = 0;
    		draw = 0;
    		// 규영이의 카드를 배정한다.
    		for(int i = 0; i < 9; i++) {
    			a[i] = stoi(st.nextToken());
    			ab[a[i]] = 1;
    		}
    		int lv = 0;
    		// 규영이가 가지지 않은 카드를 인영에게 배정한다.
    		for(int i = 1; i < 19; i++) {
    			if(ab[i] != 1) {
    				b[lv++] = i;
    			}
    		}
    		
    		DFS(0);
    		
    		System.out.println("#" + idx + " " + win + " " + lose);
    	}
    	br.close();
	}
	
	static void DFS(int lv) {
		// 만약 인영이의 카드를 9장 뽑았으면,
		if(lv == 9) {
			// 규영이의 카드와 인영이의 카드를 하나씩 비교함
			int aSum = 0, bSum = 0;
			for(int i = 0; i < 9; i++) {
				// 만약 규영이의 카드가 인영이의 카드보다 크다면 
				if(a[i] > sel[i])
					// 그 카드 2개의 합을 규영이 점수에 합함
					aSum += a[i] + sel[i];
				else
					bSum += a[i] + sel[i];
			}
			// 최종 규영의 점수가 더 높으면
			if(aSum > bSum)
				win++;	// 규영이의 승
			else if(aSum < bSum)
				lose++;
			else
				draw++;
			
			return;
		}
		for(int i = 0; i < 9; i++) {
			if(vsi[i] != 1) {
				vsi[i] = 1;
				sel[lv] = b[i];
				DFS(lv + 1);
				vsi[i] = 0;
			}
		}
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐⭐★★

후기

쉬운 문제였는데, 카드 2개의 합을 규영와 인영이의 점수에 합할 때
aSum = a[i] + sel[i];로 합 하는것이 아닌, 매번 재정의를 하고 있었다.
위 간단한 오류를 찾는데 너무 오랜 시간이 걸려 안타까운 문제였다.

개선할 점

사소한 것도 제대로 코드를 짜야한다..