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

문제

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

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

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

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

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

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

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

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

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

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

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

 

풀이방법

dfs(깊이 우선 탐색)으로 규영이가 낼 수 있는 카드의 모든 경우의 수를 구하고 각 경우의 승패를 카운트한다.

 

소스코드

package samsung;

import java.util.*;

public class s_6808 {
	static int[] v;
	static ArrayList <Integer> a;
	static ArrayList <Integer> b;
	static int cnt;
	static int[] r;
	static int a_vic;
	static int b_vic;
	
	public static void dfs(int x, int depth) {
		v[x] = 1;
		r[depth - 1] = x;
		
		if(depth == 9) {
			int a_score = 0;
			int b_score = 0;
			for(int i = 0; i <= 8; i++) {
				int a_card = a.get(i);
				int b_card = b.get(r[i] - 1);
				
				if(a_card > b_card)
					a_score += a_card + b_card;
				else
					b_score += a_card + b_card;
			}
			if(a_score > b_score)
				a_vic++;
			else if(b_score > a_score)
				b_vic++;
		}
		
		for(int i = 1; i < 10; i++) {
			if(v[i] == 0) {
				dfs(i, depth + 1);
				v[i] = 0;
			}
		}
		v[x] = 0;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int[] input = new int[19];
			a = new ArrayList();
			b = new ArrayList();
			v = new int[10];
			r = new int[10];
			cnt = 0;
			a_vic = 0;
			b_vic = 0;
			
			for(int i = 0; i < 9; i++) {
				int tmp = sc.nextInt();
				input[tmp] = 1;
			}
			
			
			for(int i = 1; i < 19; i++) {
				if(input[i] == 0)
					b.add(i);
				else
					a.add(i);
			}
			
			for(int i = 1; i < 10; i++) {
				dfs(i, 1);
			}
			System.out.println("#" + t + " " + a_vic + " " + b_vic);
		}
	}
}

 

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWgv9va6HnkDFAW0&categoryId=AWgv9va6HnkDFAW0&categoryType=CODE

SW Expert Academy