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

0. 문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWgv9va6HnkDFAW0 

SW Expert Academy

 

1. 문제 설명

1) 규영이와 인영이는 1에서 18까지의 수가 적힌 18장의 카드를 각각 9장씩 나눠 가짐

- 규영이의 9장 카드에 대한 정보가 미리 주어짐

- 나머지 카드는 인영이가 가지고 있는 카드

2) 한 라운드에 한 장씩 카드를 내서 점수를 계산함

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

- 낮은 수가 적힌 카드를 낸 사람은 아무런 점수를 얻지 않음

3) 아홉 라운드를 끝내고 총점이 더 높은 사람이 승리하게 됨

4) 규영이가 게임을 이기는 경우와 지는 경우 출력하기

 

2. 입출력

// input
4 // 테스트 케이스의 개수
1 3 5 7 9 11 13 15 17 // 9장의 카드에 대한 정보
18 16 14 12 10 8 6 4 2
13 17 9 5 18 7 11 1 15
1 6 7 9 12 13 15 17 18	

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

 

3. 코드

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class swea6808 {
	static final int cardNum = 9;
	static int[] guyoung;
	static int[] inyoung;
	static int[] sel;
	static boolean[] v = new boolean[cardNum];
	static int guScore, inScore, ans;

	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int t = 1; t <= T; t++) {
			guyoung = new int[cardNum]; // 규영 카드
			inyoung = new int[cardNum]; // 인영 카드
			for(int i = 0; i < cardNum; i++) { // 규영 카드 입력
				guyoung[i] = sc.nextInt();
			}
			Arrays.sort(guyoung);
			int gu_idx = 0;
			int in_idx = 0;
			for(int i = 1; i < (cardNum*2)+1; i++) { // 1부터 18까지 카드 중에
				if(gu_idx < 9 && guyoung[gu_idx] == i) { // 규영이가 가지고 있으면
					gu_idx++;
				} else { // 규영이가 가지고 있지 않으면
					inyoung[in_idx] = i; // 인영이에게 추가
					in_idx++;
				}
			}
			
			ans = 0; // 규영이가 이기는 횟수
			sel = new int[9]; // 인영 카드 9! 경우의 수 정리
			recursive(0);
			
			System.out.printf("#%d %d %d\n", t, ans, factorial(9)-ans);
		}
	}
	
	private static void recursive(int idx) {
		// basis part
		if(idx == sel.length) { // 다 골랐으면
			guScore = 0; // 점수 초기화
			inScore = 0;
			
			for(int i = 0; i < cardNum; i++) { // 점수 계산
				if(guyoung[i] > sel[i]) {
					guScore += (guyoung[i] + sel[i]);
				} else if(guyoung[i] < sel[i]) {
					inScore += (guyoung[i] + sel[i]);
				}
			}
			
			if(guScore > inScore) { // 규영이가 이기면 ans 1 추가
				ans++;
			} 
			return;
		}
		
		// inductive part
		for(int i = 0; i < inyoung.length; i++) {
			if(v[i] == false) {
				v[i] = true;
				sel[idx] = inyoung[i];
				recursive(idx+1);
				v[i] = false;
			}
		}
	}

	static int factorial(int n) { // 팩토리얼 계산
		// basis part
		if(n == 1) {
			return 1;
		}
		return n * factorial(n-1);
	}

}

 

실행 결과

 

4. 회고

1) 규영이가 가진 카드를 제외한 나머지 카드를 인영이가 가짐

2) 인영이가 가지고 있는 카드 9장을 순서 O 중복 X  -> 순열

3) 인영의 카드 순서가 모두 완성되면 두 카드를 비교해서 점수 계산하기

4) 규영이가 이기는 경우의 수를 구함. 규영이가 진 횟수는 9!에서 이기는 경우의 수를 뺌

 

5. Github

https://github.com/iihye/Algorithm/blob/main/SWEA/swea6808.java