Q. 6808. 규영이와 인영이의 카드게임(D3)

Q. 6808. 규영이와 인영이의 카드게임(D3)

 

0. 문제

 

D3 난이도의 문제이고, DFS와 조합을 이용한 문제라고 생각된다.

카드 뽑기 게임을 한다. 카드는 1-18까지 한 장만 있고 규영이와 인영이가 9장씩 뽑는다.

카드 게임은 두 명이 서로 한 장씩 카드를 내서 카드가 높은 사람이 두 카드의 합 만큼 점수를 가져가는 방식이고,

9번의 게임을 해서 점수가 높은 사람이 전체 게임을 이기게 된다.

규영이의 카드가 모두 주어진다면 두 명의 승패의 경우의 수를 구하는 문제이다.

---

1. 풀이

 

개인적으로 삽질을 많이 한 문제이다.. 좀 오래 고민하다보니 쉽게 풀려 슬펐다. 아래와 같은 방식으로 풀었다.

0) 먼저 규영이의 카드를 배열과 해시셋에 저장하고, 해시셋을 이용해 인영이의 카드를 찾는다.

1) 그리고 깊이를 하나씩 늘려가며 탐색을 한다.

이 때 깊이를 저장한 값을 이용해 규영이의 카드의 인덱스로 선택하고,

방문하지 않은 인영이의 카드중 하나를 다시 DFS 탐색으로 찾는다. 이 경우 모든 경우의 수를 다 볼 수 있다.

2) 종료 조건이 총 세 개 인데, 아래와 같다

2-1) 깊이가 9인 경우

2-2) 인영이의 카드가 전체 점수(1-18의 합 / 2 = 85.5)를 넘는 경우

2-3) 규영이의 카드가 전체 점수를 넘는 경우

이 때 2-3의 경우 규영이가 이긴 횟수를 계산해야 하므로 남은 경기의 수는 현재 깊이 Depth의 팩토리얼 값으로 계산했다.

3) 전체 게임의 수(9!)을 저장하고, 규영이가 이긴 횟수와 무승부 수를 이용해 인영이가 이긴 횟수를 계산한다.

 

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Solution {
 
    static BufferedReader br;
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;
     
    static HashSet<Integer> queCardsSet;
    static boolean[] inVisit;
    static int[] queCards = new int[9];
    static int[] inCards = new int[9];
    static int Win, Draw;
    static int wholeGameCnt = 362880; // 9!
    static int winScore = 85; // 86점부터 전체 점수의 반 이상
     
    static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        queCardsSet = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            queCards[i] = Integer.parseInt(st.nextToken());
            queCardsSet.add(queCards[i]);
        }
    }
     
    static void pro(int tc) throws Exception{
         
        int cnt = 0;
         
        inVisit = new boolean[9];
         
        for (int i = 1; i < 19; i++) {
            if (queCardsSet.contains(i)) continue;
            inCards[cnt++] = i;
        }
         
        Win = Draw = 0;
        dfs(0, 0, 0);
        sb.append(String.format("#%d %d %d\n", tc, Win, wholeGameCnt - Draw - Win));
    }
     
    static void dfs(int depth, int queScore, int inScore) {
 
        if (depth == 9) {
            if (queScore > inScore) Win++;
            else if (queScore == inScore) Draw++;
            return;
        }
         
        if (inScore > winScore) return;
        if (queScore > winScore) {
             
            int round = 1;
            int factorial = 9 - depth;
            while (factorial > 1) { // (9 - depth)!
                round *= factorial;
                factorial--;
            }
            Win += round;
            return;
        }
         
        for (int i = 0; i < 9; i++) {
            if (inVisit[i]) continue;
             
            int curSum = queCards[depth] + inCards[i];
            int curQueScore = queScore;
            int curInScore = inScore;
            if (queCards[depth] > inCards[i]) curQueScore += curSum;
            else curInScore += curSum;
             
            inVisit[i] = true;
            dfs (depth + 1, curQueScore, curInScore);
            inVisit[i] = false;
             
        }
         
    }
     
    public static void main(String[] args) throws Exception{
         
        br = new BufferedReader(new InputStreamReader(System.in));
//      br = new BufferedReader(new InputStreamReader(new FileInputStream("res/input.txt")));
        int T = Integer.parseInt(br.readLine());
        for(int tc = 1; tc <= T; tc++) {
            input();
            pro(tc);
        }
        System.out.println(sb);
         
    }
 
}

---

2. 시간복잡도 계산

 

1) 전체 탐색 횟수는 9! * 2이고, 725760이다.

이 문제의 제한시간은 6초로 꽤 넉넉한 편이고, 나는 위 방식으로 가지치기를 최대한 해서 1.1초 정도에 풀었다.

---

3. 성능 개선 방안

 

1) 앞에서 설명했듯이, 한 명의 승리 횟수와 무승부 수를 이용해 나머지 친구의 승리 횟수를 계산했다.

2) 또한 전체 점수의 반 이상을 넘겼을 경우 다음 게임을 진행할 필요가 없으므로 이 역시 코드에 반영했다.