백준 16986 인싸들의 가위바위보

문제링크

https://www.acmicpc.net/problem/16986

문제

키포인트

• N이 1~9의 값을 가지므로 지우가 내는 가위바위보 순서는 최대 9!= 362880 가지 입니다. 따라서 브루트 포스로 해결이 가능합니다.

시행착오

처음에 문제에서 자신이 참여할 20경기에서 낼 손동작 수가 주어진다고 하여 각 사람이 참여하는 경우에만 각 사람의 가위바위보 순서에 대한 인덱스를 증가시키며 진행하려 하였습니다.
그런데! 문제 밑에서 비둘기집 원리로 20경기가 입력으로 주어졌을때 반드시 승자가 정해진다고 말하기에 전체 라운드에 대한 진행을 의도하는것 같아 그렇게 하였습니다만..
결국 각 사람이 참여한 라운드에 대해서만 index값을 올려주며 진행하는게 맞았습니다.

코드

#include <iostream>
using namespace std;
int n, k;
int rule[11][11];
int order[3][20];
bool vi[11];

int nextturn(int a, int b) {
	for (int i = 0; i < 3; i++) 
		if (i != a && i != b) return i;
	
}

bool run() {
	int wincnt[3],turnidx[3];
	int winner = 0, challenger = 1;
	for (int i = 0; i < 3; i++) {
		wincnt[i] = turnidx[i] = 0;
	}
	
	while (true) {
		int next = nextturn(winner, challenger);
		int wdo = order[winner][turnidx[winner]++];
		int cdo = order[challenger][turnidx[challenger]++];
		if (rule[wdo][cdo] == 1) {
			if (winner < challenger) winner = challenger;
		}
		else if (rule[wdo][cdo] == 0) {
			winner = challenger;
		}
		if (++wincnt[winner] == k) {
			if (winner != 0) return false;
			else return true;
		}
		if (turnidx[0] == n) return false;
		challenger = next;
	}
}

bool sel(int cnt) {
	if (cnt == n) {
		return run();
	}
	for (int i = 1; i <= n; i++) {
		if (!vi[i]) {
			vi[i] = true;
			order[0][cnt] = i;
			if(sel(cnt + 1)) return true;
			vi[i] = false;
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> rule[i][j];
		}
	}
	for (int i = 1; i <= 2; i++) {
		for (int j = 0; j < 20; j++) {
			cin >> order[i][j];
		}
	}
	cout<<sel(0);
}

후기

비슷한 유형의 문제를 몇 번 풀어봐서 무난하게 해결했습니다.