백준 g3 16986 인싸들의 가위바위보 c++

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

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

 

헷갈릴 수 있는 요소

 

문제가 헷갈린다는 평이 많다. 그러니 문제를 읽고 나서 풀기 전에 꼭 예제 밑에 있는 노트를 읽어보자.

• 주어지는 경희, 민호의 손동작 순서는 라운드별이 아닌, 자신이 경기를 하나 참여할 때마다 하나씩 쓰는 것.
  • ex. 지우vs경희, 경희vs 민우 경기를 차례대로 진행한다고 가정했을 때, 2번째 경기에서 민우는 자신의 두번째 손동작을 내는 것이 아니라, 첫 번째 손동작을 낸다. 그 이후에 경기에 참여하게 되면, 몇 번째 경기이냐는 상관없이 두번째 손동작을 낸다.
• 두 사람이 비겼을 경우에는 경기 진행 순서상 뒤인 사람이 승리한다.
  • 여기서 경기 진행 순서란 지우 - 경희 - 민호이다. 따라서 만약 경희 vs. 지우 경기가 비겼다면 경희의 승리이다.
  • 나는 경기 진행 순서를 지우-경희-민호가 아니라, A vs B 일 때 B라고 잘못 이해해서 시간을 많이 날렸다. 예시에도 나와있는 내용이니 예시가 주어졌으면 예시를 꼼꼼히 보자..

문제 설명

• input
  • 손동작 N개, 승리 횟수 K, 손동작 N*N들의 상성 (Ai,j가 2면 i승, 1이면 비김, 0이면 패)
  • 경희, 민호가 낼 손동작 20개
• output
  • 지우가 매 경기마다 손동작을 다르게 낼 때, 승리할 수 있으면 1 그렇지 않으면 0 출력

수도 코드

dfs(a vs b) // a vs b 경기 진행
	if ans == 1 // 이미 우승 가능하다고 판별났으므로 더 할 필요 X
    	return
    if 우승횟수[지우] == K
    	ans = 1
        return
    else if 우승횟수[경희] == K || 우승횟수[민호] == K
    	return
    
    for(i: 1~N 지우가 사용할 손동작)
    	if used[i]
        	continue
        a의 손동작 vs b의 손동작
        
        used[i] = 1
        우승횟수[winner]++
        dfs(winner, 나머지)
        
        used[i] = 0
        우승횟수[winner]--

 

 

전체 코드

/*boj g3 16986 인싸들의 가위바위보*/
#include <iostream>
#define MAXN 10
using namespace std;

int N, K;
int wins[3]; // 0 지우, 1 경희, 2 민우
int compatibility[MAXN][MAXN];
int used[MAXN];
int cur1 = 0;
int cur2 = 0;

int player1[22]; // 1이면 경희, 2면 민우, 0은 비어있음
int player2[22];

int ans = 0;

void input() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> compatibility[i][j];
        }
    }

    for (int j = 0; j < 20; j++) {
        cin >> player1[j];
    }

    for (int j = 0; j < 20; j++) {
        cin >> player2[j];
    }
}

int gesture(int a, int i) {
    int res = -1;
    if (a == 0) { // 지우의 gesture
        res = i;
    } else if (a == 1) { // 경희의 gesture
        res = player1[cur1];
        cur1++;
    } else if (a == 2) { // 민호의 gesture
        res = player2[cur2];
        cur2++;
    }

    return res;
}

int getOther(int a, int b) {
    int check[3] = {0, 0, 0};
    check[a] = 1;
    check[b] = 1;

    for (int i = 0; i < 3; i++) {
        if (check[i] == 0) return i;
    }
}

void dfs(int a, int b) {
    if (ans == 1) return; // 이미 가능으로 판별남

    if (wins[0] == K) {
        ans = 1;
        return;
    } else if (wins[1] == K || wins[2] == K) {
        return;
    }

    if (cur1 >= 20 || cur2 >= 20) return;

    if (a == 0 || b == 0) { // 지우 경기
        for (int i = 1; i <= N; i++) {
            if (used[i]) continue;

            int x = gesture(a, i);
            int y = gesture(b, i);

            int winner;
            int fightRes = compatibility[x][y];

            if (fightRes == 2)
                winner = a;
            else if (fightRes == 1)
                winner = a > b ? a : b;
            else
                winner = b;

            used[i] = 1;
            wins[winner]++;
            int other = getOther(a, b);

            dfs(winner, other);
            wins[winner]--;
            used[i] = 0;

            if (a == 1 || b == 1)
                cur1--;
            else if (a == 2 || b == 2)
                cur2--;

            if (ans) return;
        }
    } else { // 경희 민호 경기
        int x = gesture(a, -1);
        int y = gesture(b, -1);

        int winner;
        int fightRes = compatibility[x][y];

        if (fightRes == 2)
            winner = a;
        else if (fightRes == 1)
            winner = a > b ? a : b;
        else
            winner = b;
        wins[winner]++;

        dfs(winner, 0); // 다음은 승자 vs 지우
        wins[winner]--;
        cur1--;
        cur2--;
    }
}

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

    dfs(0, 1);

    cout << ans << "\n";
}