[BOJ] 16986 - 인싸들의 가위바위보

[백준] 16986 - 인싸들의 가위바위보

풀이 시간 : 174분째(모의고사라서 두 문제를 다 읽은 후 풀었다. 첫번째 문제를 푼 다음 77분째)

잘못된 구현

처음에 시간복잡도가 굉장히 클 것 같아서 DP로 풀기 위해 접근했다.(그러나 자꾸 답은 나오지 않았다..)
답이 나오지 않아 차라리 아예 완전탐색으로 접근해보자 하고 메모이제이션 하는 코드를 지우고 실행해보니 답이 제대로 나왔다.
다행히 DP문제가 아니어서 망정이지만 만일 정말 DP문제였다면.. 머리를 싸매고 고생하다가 타임오버했을 것이다..

잘못된 문제 이해

문제에서 주어지는 20개의 손동작을 20개의 라운드가 있고 그 때 어떤 손동작을 내는 것인지 나타낸 것이라 이해했다.
분명 사소한 조건도 손으로 써가며 잘 따져봤다고 생각했는데.. 이해를 잘못했기 때문에 코드를 아무리 뜯어봐도 문제는 나오지 않는게 당연하다.

교훈

반드시 문제의 모든 조건을 하나하나 따지며 이해하고 풀도록 하자.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <string.h>
#define INF 987654321
using namespace std;
typedef tuple<int, int, int> T;

// dp[이전까지 사용한 손동작의 갯수][현재 라운드][현재 결투하는 조합]
int n, k, power[10][10], B[25], C[25];

//team : (1, 2), (1, 3), (2, 3)
bool go(int pre, int idx_B, int idx_C, int team, int b_win, int c_win, int ret) {
	if (c_win >= k || b_win >= k) return false;
	if (ret >= k)
		return true;
	if (team == 2) { // 지우가 없을 경우 승패는 정해져있음.
		if (idx_B >= 20 || idx_C >= 20) return false;
		bool winner = power[C[idx_C]][B[idx_B]] > 0;
		if (winner) return go(pre, idx_B + 1, idx_C + 1, winner ? 1 : 0, b_win, c_win + 1, ret);
		else return go(pre, idx_B + 1, idx_C + 1, winner ? 1 : 0, b_win + 1, c_win, ret);
	}
	bool rtn = false;
	for (int i = 1; !rtn && i <= n; i++) {
		if (pre & (1 << i)) {
			continue;
		}
		int p = team == 0 ? B[idx_B] : C[idx_C];
		if (power[p][i] > 0) { // 상대방이 이길 경우
			if (team == 0) {
				rtn |= go(pre | (1 << i), idx_B + 1, idx_C, 2, b_win + 1, c_win, ret);
			}
			else rtn |= go(pre | (1 << i), idx_B, idx_C + 1, 2, b_win, c_win + 1, ret);
		}
		else {
			if (team == 0) {
				rtn |= go(pre | (1 << i), idx_B + 1, idx_C, 1, b_win, c_win, ret + 1);
			}
			else rtn |= go(pre | (1 << i), idx_B, idx_C + 1, 0, b_win, c_win, ret + 1);
		}
	}
	return rtn;
}

int main(void) {
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", power[i] + j);
		}
	}
	for (int i = 0; i < 20; i++) {
		scanf("%d", B + i);
	}
	for (int i = 0; i < 20; i++) {
		scanf("%d", C + i);
	}

	printf("%d", go(0, 0, 0, 0, 0, 0, 0));
	return 0;
}