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

▶문제설명

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

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

▶Hint

---

1부터 18까지의 숫자로 이루어진 카드가 있을 때,

규영이가 9장, 인영이도 9장으로 나눠 가지고 간단한 카드 게임을 한다.

[게임 규칙]

각자 가지고 있는 카드들 중 하나를 뽑아서 낸다.

카드의 번호가 더 큰 사람이 승리하며, 

승리자는 제출한 카드 두 장의 합을 점수로 얻는다.

규영이는 카드를 받은 순서대로 제출하는 것으로 고정한다.

인영이는 9!의 모든 경우의 수로 카드를 제출할 수 있다.

이 게임에서 규영이가 승리하는 경우의 수와, 지는 경우의 수를 계산하여 출력해야한다.

한 사람이 얻은 점수가 1부터 18까지의 모든 수를 더한 값의 절반을 넘어가면 게임 결과는 이미 정해진다.

만약 5번째 턴에서 규영이의 점수가 해당 값의 절반을 넘어가서 승리했다면

그 뒤의 4x3x2x1번의 게임 결과는 볼 필요도 없이 규영이의 승리가 된다.

이를 이용하여 가지치기를 하면 수행 시간을 줄일 수 있다.

규영이의 카드를 보고 인영이에게 카드를 할당할 때

그리고 모든 경우의 수를 확인하기 위해 dfs를 수행할 때,

선택된 숫자 카드를 구분하기 위한 check배열을 하나 만들어 활용한다.

▶Solution

---

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
 
int deckA[9], deckB[9];
bool checkNum[19];
int win, lose;
int total = 18 * 19 / 2;
 
void input() {
    int index = 0;
 
    for (int i = 1; i <= 18; i++)
        checkNum[i] = false;
 
    for (int i = 0; i < 9; i++) {
        scanf("%d", &deckA[i]);
        checkNum[deckA[i]] = true;
    }
 
    for (int i = 1; i <= 18; i++) {
        if (checkNum[i] == false)
            deckB[index++] = i;
    }
 
    win = lose = 0;
    memset(checkNum,0,sizeof(checkNum));
}
 
void calc(int index, int scoreA, int scoreB) {
    if (scoreA > total/2 || scoreB > total/2) {
        int result = 1;
        
        for (int i = index; i < 9; i++)
            result *= 9-i;
 
        if (scoreA > total / 2)
            win += result;
        else
            lose += result;
 
        return;
    }
    else 
    {
        for (int i = 0; i < 9; i++) {
            if (checkNum[deckB[i]] == false) {
                checkNum[deckB[i]] = true;
                
                if (deckA[index] > deckB[i])
                    calc(index + 1, scoreA + deckA[index] + deckB[i], scoreB);
                else
                    calc(index + 1, scoreA, scoreB + deckA[index] + deckB[i]);
 
                checkNum[deckB[i]] = false;
            }
        }
    }
}
 
int main() {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++)
    {
        input();
 
        calc(0, 0, 0);
 
        printf("#%d %d %d\n", t, win, lose);
    }
    return 0;
}