[SWEA] 6808번: 규영이와 인영이의 카드게임 (Java)

 

---

 

문제

SW Expert Academy

 

 

개념

순열, 백트래킹

 

 

실행 결과

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

 

 

 

 

구현 코드(Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Solution {
	static int winCount = 0;
	static int loseCount = 0;

	// swap permutation을 위한 스왑 함수
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	// backtracking: swap permutation 이용한 스왑 재귀
	// https://www.jiwon.me/permutations/
	public static void permute(int[] iny, int start, int end, int[] gyu) {
		if (start == end) {
			calculateSum(gyu, iny);
		} else {
			for (int i = start; i <= end; i++) {
				swap(iny, start, i);
				permute(iny, start + 1, end, gyu);
				swap(iny, start, i);
			}
		}
	}

	// 규영이가 이기고 지는 횟수를 계산
	public static void calculateSum(int[] gyu, int[] iny) {
		int qyuSum = 0;
		int inySum = 0;
		for (int j = 0; j < 9; j++) {
			if (gyu[j] > iny[j]) {
				qyuSum += gyu[j] + iny[j];
			} else {
				inySum += gyu[j] + iny[j];
			}
		}

		if (qyuSum > inySum) {
			winCount++;
		} else {
			loseCount++;
		}
	}

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

		for (int test_case = 1; test_case <= T; test_case++) {
			int[] gyu = new int[9]; // 규영이 카드
			boolean[] cards = new boolean[19]; // 1~18 카드 사용 나타낼 불리언 배열

			// 규영이가 낸 카드 입력
			for (int i = 0; i < 9; i++) {
				gyu[i] = sc.nextInt();
				cards[gyu[i]] = true; // 카드 사용 처리
			}

			int[] iny = new int[9]; // 인영이 카드
			int idx = 0;

			// 인영이 카드 찾기
			for (int i = 1; i <= 18; i++) {
				if (!cards[i]) {
					iny[idx++] = i;
				}
			}

			winCount = 0;
			loseCount = 0;

			permute(iny, 0, 8, gyu);

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

 

 

 

 

코드 설명

카드는 1~18의 총 18개가 있다.

규영이가 9장을 임의로 고르는 경우, 나머지 9장은 자동으로 인영이가 가지게 된다. 

총 9!개의 경우의 수 중 규영이가 가진 카드의 합이 더 큰 경우의 수를 구하는 문제이므로 조합을 이용하면 된다.

 

순열(Permutation)

서로 다른 n개의 원소를 가지는 어떤 집합에서 r개의 원소를 순서를 고려하여 선택하는 것이다. 

문제에서는 카드를 뽑는 순서가 경기 결과에 영향을 미치므로 

여기서는 n = 18, r = 9라고 할 수 있고, 카드는 숫자 당 하나씩만 존재하고 하나를 뽑을 경우 해당 카드는 뽑을 수 없으므로 중복순열은 아니다.

 

백트래킹(BackTracking)

순열은 swap 함수를 구현해서 백트래킹을 통해 구할 수 있다.

 

 

 

배열의 원소 위치를 차례차례 교체(스왑)하는 방식으로 모든 경우의 수를 구할 수 있다.

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 

permute 함수에서 위 함수를 사용해서 백트래킹을 구현한다.

끝까지 다 돌았으면 calculateSum 함수를 호출하여 게임 승패를 판단하도록 한다.

아래로는 재귀호출로 완전 탐색을 구현하여, 인영이가 가질 수 있는 카드의 순열을 전부 구한다.

 

public static void permute(int[] iny, int start, int end, int[] gyu) {
    if (start == end) {
        calculateSum(gyu, iny);
    } else {
        for (int i = start; i <= end; i++) {
            swap(iny, start, i);
            permute(iny, start + 1, end, gyu);
            swap(iny, start, i);
        }
    }
}

 

 

 

---

참고자료 

조합과 순열