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

무지성 DFS 바로 컽당함 ;;

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

SW Expert Academy

#include <cstdio>
#include <cstring>
int T;
int arr[19];
int G[10];	// 규영이가 가진 9개 카드 
int I[10];	// 인영이가 가진 9개 카드 (후보)
int choice[10];	// 순열 
int flag[10];
int win, lose;

void init()
{
	memset(arr, 0, sizeof(arr));
	memset(G, 0, sizeof(G));
	memset(I, 0, sizeof(I));
	memset(choice, 0, sizeof(choice));
	memset(flag, 0, sizeof(flag));
	win = lose = 0;
}

void input()
{
	for (int i = 1; i <= 9; i++) {
		scanf("%d", &G[i]);
		arr[G[i]] = 1;
	}

	// 인영이가 가질 수 있는 카드 정보 
	int num = 1;
	for (int i = 1; i <= 18; i++) {
		if (arr[i] == 0) I[num++] = i;	
	}
}


void DFS(int n, int gyu_win, int in_win)
{
	if (n > 9) {
		if (gyu_win > in_win) win++;
		else if (gyu_win < in_win) lose++;
		return;
	}

	for (int i = 1; i <= 9; i++) {
		if (flag[i]) continue;
		flag[i] = 1;
		if (I[i] < G[n]) DFS(n + 1, gyu_win + G[n] + I[i], in_win);
		if (I[i] > G[n]) DFS(n + 1, gyu_win, in_win + G[n] + I[i]);
		flag[i] = 0;
	}
}

int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		init();
		input();
		DFS(1, 0, 0);	// 몇번째 판, 규영이김, 인영이김 
		printf("#%d %d %d\n", t, win, lose);
	}
	return 0;
}

인영이 카드 순서 다 정하고 두 명의 점수를 비교하면 바로 시간초과 컽당한다. 

맞왜틀 맞왜틀 주문 2번 외우고 사람들이 남긴 댓글 보고 풀었다. ㅋㅋㅋ..

 

n번째 판에서 게임을 진행할 때, 규영이가 이겼으면 규영 점수 + (규영 + 인영 카드 숫자) / 인영이가 이겼으면 인영 점수 + (규영 + 인영 카드 숫자) 이렇게 파라미터를 구성해서 n > 9가 되었을 경우에만 규영이가 이겼는지 졌는지 판단해주면 된다.