[C++]백준 16986번 : 인싸들의 가위바위보

www.acmicpc.net/problem/16986

16986번: 인싸들의 가위바위보

1. 접근

경우의 수마다 체크해야할 것이

1) 지우가 K번 이겼는지

2) 다른 두 명이 먼저 K번 이겼는지

3) 지우가 중복하지 않게 손동작을 했는지

4) 이번 가위바위보가 몇 번째 차례인지

라고 생각하여 재귀로 풀어야 한다고 생각하고 접근했다.

 

2. 오해

경희, 민호의 20번 손동작에 대한 정보가 입력으로 주어지는데,

해당 순번은 가위바위보의 총 turn 수가 아닌 개개인의 turn에 따라 내는 손동작이다.

따라서 앞서 생각한 4)은 각각이 이번에 가위바위보가 몇번 째 차례인지 따로 따로 생각해야한다.

 

문제를 읽고 아무리해도 테스트케이스가 맞질 않아 질문으로 알아냈는데 아직도 문제에서 오해하지 않도록 주어지지 않았다고 생각한다...

 

3. 재구성

조건의 분기를

1) 지우가 이번에 가위바위보를 하는지 (이것에 따라 p1==지우, p2==지우, p1!=지우&&p2!=지우 3분기)

2) 그에 따라 이번 두 참가자의 손동작을 도출

2-1. 지우가 있다면 현재까지 내지 않은 손동작을 고른다. (for문)

2-1. 경희, 민호의 경우에는 각자의 turn에 맞는 손동작을 고른다.

3) 두 참가자의 승부 결과에 따른 다음 재귀

 

로 해서 코드가 길어지고 가독성이 좋지 않았는데

검색을 통해 알아낸 다음과 같은 코딩으로 코드도 줄이고 가독성도 높혔다.

 

(for문)

1) 두 참가자의 손동작을 도출

1-1. 지우가 참가하고 있다면 내지 않은 손동작에 대해 순차적으로 반복문

1-2. 지우가 참가하고 있지 않다면 for문 마지막 index로 갱신하여 반복문 1번수행

2) 두 참가자의 승부 결과에 따른 다음 재귀

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int N, K, map[10][10], h[3][20];
int win[3] = { 0, }, cnt[3] = { 0, };
bool check[10] = { false, };
int ans = 0;

bool checkHistory(int n){
	for (int i = 0; i < cnt[0]; i++)
		if (h[0][i] == n)
			return true;

	return false;
}

void dfs(int p1, int p2){

	if (win[1] == K || win[2] == K)
		return;

	if (win[0] == K){
		cout << 1;
		exit(0);
		return;
	}

	for (int i = 1; i <= N; i++){
		if (p1 != 0 && p2 != 0)
			i = N;
		else{
			if (checkHistory(i))
				continue;

			h[0][cnt[0]] = i;
		}
		
		int res = map[h[p1][cnt[p1]]][h[p2][cnt[p2]]];
		int winner;

		if (res == 2) winner = p1;
		else if (res == 1) winner = p1 > p2 ? p1 : p2;
		else winner = p2;

		cnt[p1]++;
		cnt[p2]++;
		win[winner]++;
		dfs(winner, 3 - (p1 + p2));
		cnt[p1]--;
		cnt[p2]--;
		win[winner]--;
	}

	return;
}

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 >> map[i][j];

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

	dfs(0, 1);

	cout << 0;

	return 0;
}