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

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

 

www.acmicpc.net

풀이

가위바위보 손동작 수가 N이라면 지우는 [1, 2, 3, ... , N] 을 낼 수 있다. 따라서 지우가 낼 손동작의 순서를 모두 구해서 확인해보면 해결할 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
int a[10][10];
int jw[10], kh[20], mh[20];

bool simulation() {    
    int jw_idx = 0, kh_idx = 0, mh_idx = 0;
    int jw_win = 0, kh_win = 0, mh_win = 0;
    // 다음 차례에 가위바위보 할 사람을 가리키는 변수
    // 0: 지우, 1: 경희, 2: 민호
    int rest = 2;

    while (true) {
        // 지우가 k번 이긴 경우
        if (jw_win == k) return true;
        // 지우가 모든 손동작을 1번씩 하고도 k번 못이긴 경우
        if (jw_idx == n || kh_win == k || mh_win == k) return false;
        if (rest == 2) {
            int v = a[jw[jw_idx++]][kh[kh_idx++]];
            if (v == 2) {
                jw_win++;
                rest = 1;
            }
            else {
                kh_win++;
                rest = 0;
            }
        }
        else if (rest == 1) {
            int v = a[jw[jw_idx++]][mh[mh_idx++]];
            if (v == 2) {
                jw_win++;
                rest = 2;
            }
            else {
                mh_win++;
                rest = 0;
            }
        }
        else {
            int v = a[kh[kh_idx++]][mh[mh_idx++]];
            if (v == 2) {
                kh_win++;
                rest = 2;
            }
            else {
                mh_win++;
                rest = 1;
            }
        }
    }
    return false;
}

int main() {
    ios_base::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 >> a[i][j];
    for (int i = 0; i < 20; i++) cin >> kh[i];
    for (int i = 0; i < 20; i++) cin >> mh[i];
    // 지우는 1 ~ N 까지 1번씩만 낸다
    for (int i = 0; i < n; i++) jw[i] = i + 1;

    bool find = false;

    // 지우가 낼 수 있는 모든 경우를 확인
    do {
        if (simulation()) {
            find = true;
            cout << "1\n";
            break;
        }
    } while (next_permutation(jw, jw+n));
    if (!find) cout << "0\n";
    return 0;
}