[SWEA 6898] 규영이와 인영이의 카드게임

문제

• SWEA 0898번
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

이 문제는 순열과 관련된 문제이다.
문제에서 1부터 18까지의 카드를 각자 9개씩 나누어 가진다고 하고 규영이는 9개의 고정된 입력값이 들어온다. 따라서 전체 카드에서 규영이가 가진 만큼을 뺀 나머지 카드를 인영이가 가지게 된다.
이렇게 인영이가 가질 수 있는 배열만 모아논 myCard배열을 만든 후, 각 카드들이 순서가 어떻게 되느냐에 따라서 규영이와의 게임의 결과가 달라지게 된다. 따라서 9개의 서로 다른 카드를 순서있게 정하는 방법인 순열을 적용하도록 한다.
함수 per()에서 카드를 한장씩 뽑아가면서 순열을 만드는데 만약 카드를 다 뽑은 경우에는 규영이와 i=0에 위치한 카드부터 끝까지 비교해가면서 각자의 이긴 점수를 저장한 후에 누가 이기고 졌는지를 체크한다. 모든 재귀를 반복하게 되면 나올 수 있는 모든 경우의 수를 다 따져본 것이므로 이때 구한 규영이가 이기는 경우와 질 경우를 출력해준다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Swea_6808 {

	static final int SIZE = 9; // 각자 카드 수
	static int[] allCard; // 전체 카드 1~18
	static int[] partner; // 규영이 고정 카드
	static int[] myCard; // 전체-규영 카드(인영카드)
	static int[] numbers; //뽑은 카드
	static boolean[] isSelected;
	static int win, lose;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int tc = 0; tc < T; tc++) {
			partner = new int[SIZE];
			allCard = new int[SIZE * 2 + 1];
			numbers = new int[SIZE];
			isSelected = new boolean[SIZE];
			win = 0;
			lose = 0;

			// 규영 고정
			for (int i = 0; i < 9; i++) {
				partner[i] = sc.nextInt();
				// 전체 카드에 해당 카드 인덱스를 이미 사용됐다고 표시
				allCard[partner[i]] = -1;
			}

			myCard = new int[SIZE];
			// 사용되지 않은 카드 배열 만들기
			for (int i = 0; i < SIZE; i++) {
				for (int j = 1; j < allCard.length; j++) {
					if (allCard[j] != -1) { //사용안했다면
						myCard[i] = j;
						allCard[j] = -1;
						break;
					}
				}
			}

			// 9!만들기
			per(0);
			System.out.println("#"+(tc+1)+" "+win+" "+lose);
		}
	}

	//9개의 카드를 순서있게 뽑기(순열)
	public static void per(int cnt) { // cnt: 현재까지 뽑힌 개수
		// 다 뽑았으면
		if (cnt == SIZE) {
			// 값 비교
			int my_sum = 0; //인영이 점수
			int part_sum = 0; //규영이 점수

			// 9번 라운드
			for (int i = 0; i < SIZE; i++) {
				if (numbers[i] > partner[i]) //인영이가 이겼다면
					my_sum += numbers[i] + partner[i];
				else if (numbers[i] < partner[i])//규영이 이겼다면
					part_sum += numbers[i] + partner[i];
				else //비겼다면
					continue;
			}
			
			if(part_sum > my_sum) win++; //규영이가 이김
			else if(part_sum < my_sum) lose++; //규영이가 짐
			return; // 재귀 탈출
		}

		for (int i = 0; i < SIZE; i++) {
			// 중복 확인
			if (isSelected[i])
				continue;

			numbers[cnt] = myCard[i]; // 해당숫자 사용
			isSelected[i] = true;

			per(cnt + 1); // 다음 자리 순열 뽑기
			isSelected[i] = false;
		}
	}
}