인싸들의 가위바위보 (16986)

1. 문제

문제 링크

2. 풀이

일단 지우는 모두 다른 숫자를 내서 이겨야하기 때문에
k > n이면 볼 것도 없이 정답은 0입니다.
k번 이겨야 하는데 가위바위보 종류는 k보다 적으면
비둘기집 원리에 의해 적어도 한 번 같은 종류의 숫자를 내기 때문입니다.

그래서 어떻게 풀어야하나?

이 문제는 수열을 통해 모든 경우의 수를 다 해봐야하는 문제입니다.
처음엔 이겨도 나머지 라운드는 패배할 수도 있지만,
처음엔 져도 나머지 라운드는 승리할 수도 있는 경우가 있기 때문입니다.

1. 지우가 낼 수 있는 가위바위보 순열 만들기
2. 가위바위보 시뮬레이션 돌리기

만약 지우가 이길 수 있는 경우를 찾았으면 나머지 경우는 보지도 않고 종료하면 됩니다.

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

int n, k;
int winLose[10][10];
int rsp[20][3];
int scores[3];
int ptr[3];
int used[10];
int ans = 0;

// 가위바위보 게임 시뮬레이션
void go(int p1, int p2) {
	// 지우가 이겼을 때
	if (scores[0] >= k) {
		ans = 1;
		return;
	}

	// 경희나 민호가 이겼을 때
	if (scores[1] >= k || scores[2] >= k) return;

	// 지우가 n판 안에 승리하지 못했을 때
	if (ptr[0] > n) return;

	if (p1 > p2) swap(p1, p2);

	// p1이 이겼을 때
	if (winLose[rsp[ptr[p1]++][p1]][rsp[ptr[p2]++][p2]] == 2) {
		scores[p1]++;
		go(p1, 3 - p1 - p2);
	}
	// p2가 이겼을 때
	else {
		scores[p2]++;
		go(p2, 3 - p1 - p2);
	}
}

void slove(int depth) {
	// ans가 1일 때 다른 경우의 수는 보지도 않고 종료
	if (ans) return;

	if (depth == n) {
		// 가위바위보 시뮬레이션
		go(0, 1);
		
		// 각 포인터와 점수 초기화
		ptr[0] = ptr[1] = ptr[2] = 0;
		scores[0] = scores[1] = scores[2] = 0;

		return;
	}

	// 순열 만들기
	for (int i = 1; i <= n; i++) {
		// ans가 1일 때 다른 경우의 수는 보지도 않고 종료
		if (ans) return;

		if (used[i]) continue;

		rsp[depth][0] = i;
		used[i] = 1;
		slove(depth + 1);
		used[i] = 0;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;

	if (k > n) {
		cout << 0;
		return 0;
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> winLose[i][j];

	for (int i = 1; i <= 2; i++)
		for (int j = 0; j < 20; j++)
			cin >> rsp[j][i];

	slove(0);

	cout << ans;

	return 0;
}