16986. 인싸들의 가위바위보

문제 링크

16986번: 인싸들의 가위바위보 (acmicpc.net)

 

풀이

지우가 가위바위보에서 매 판마다 서로 다른 손동작을 내서 우승할 수 있는지를 묻고 있다. 규칙을 찾는다던가 해서 지우의 최적의 손동작 순서를 찾는다기엔 경희와 민호의 손동작 순서, 가위바위보 결과에 따른 다음 경기자 판별 등, 고려할 요소가 많고 복잡해지니 백트래킹을 활용한 브루트 포스로 푸는 게 속 편하다. 주어지는 숫자가 큰 수도 아니니 더더욱.

 

백트래킹을 활용한 풀이는 지우의 가능한 손동작 순서를 전부 찾고, 찾은 순서 각각으로 가위바위보 시뮬레이션을 돌려보는 것이다. 그러다 우승하는 시나리오가 나타나면 1, 전부 돌려봐도 안 나타나면 0을 출력하면 된다.

 

전부 다른 손동작으로 승수를 채워야 하는 특성상, 가능한 손동작 수는 목표 승수 이상이어야 한다. 즉, N < K이면 승리하기 위한 손동작 수가 모자라 절대 승리할 수 없으니 이는 시작부터 걸러내도록 한다.

 

그리고 주어진 경희와 민호의 손동작은 앞에서부터 건너뛰지 않고 순서대로 사용해야 한다. 예제 2를 예시로 들자면, 주어진 민호의 손동작이 1경기는 3, 2경기는 2, 3경기는 1, ... 이런 식으로 내서 민호가 참가하지 않는 1경기의 손동작 3은 건너뛰고 2경기에서 2를 낸다는 뜻이 아니라, 2경기부터 3을 낸다는 뜻이다. 요컨대, 자신이 참가하는 경기만 따져서 해당 손동작을 순서대로 낸다는 뜻이다.

 

시간 복잡도

가능한 손동작이 \(N\)개이므로, 지우가 가능한 서로 다른 손동작의 순서는 총 \(N!\)개이다. 각각의 손동작에 대하여 가위바위보 시뮬레이션을 돌리지만, 비둘기집의 원리에 의해 \(3(K-1)+1\)번의 경기를 치르면 우승자가 결정되는데, \(K\)의 최댓값 6을 넣었을 경우에도 경기 횟수는 최대 16회로 \(N!\)에 비하면 매우 적다. 따라서 아래 소스코드의 시간 복잡도는 \(O(N!)\)이다.

 

소스코드

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

int N, K, ans;
int A[10][10];

// 가위바위보에서 낼 손동작을 저장하는 2차원 배열
// 지우: RPSOrder[0], 경희: RPSOrder[1], 민호: RPSOrder[2]
int RPSOrder[3][20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, };

// 가위바위보 참가자의 참가 순서, 손동작 순서 인덱스, 이긴 횟수를 저장하는 구조체
typedef struct player {
    int order;
    int idx;
    int wins;
} Player;

// 가위바위보 결과를 판정하는 함수
// true면 n1을 낸 사람의 승리, false면 n2를 낸 사람의 승리
bool judgeRPS(int n1, int n2) {
    if(A[n1][n2] == 2) return true;
    else return false;
}

// 가위바위보를 실행하는 함수
// 지우가 이겼으면 true, 아니면 false 리턴
bool RPS() {
    Player plr[3] = { {0, 0, 0}, {1, 0, 0}, {2, 0, 0} };
    Player* fir = &plr[0];
    Player* sec = &plr[1];
    Player* thr = &plr[2];
    
    while(plr[0].wins < K && plr[1].wins < K && plr[2].wins < K) {
        if(judgeRPS(RPSOrder[fir->order][fir->idx++], RPSOrder[sec->order][sec->idx++])) {
            fir->wins++;
            swap(sec, thr);
        }
        else {
            sec->wins++;
            swap(fir, thr);
        }
        
        if(fir->order > sec->order) {
            swap(fir, sec);
        }
    }
    
    if(plr[0].wins == K) return true;
    else return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> K;
    if(N < K) {
        cout << 0;
        return 0;
    }
    
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            cin >> A[i][j];
        }
    }
    
    for(int i = 1; i <= 2; i++) {
        for(int j = 0; j < 20; j++) {
            cin >> RPSOrder[i][j];
        }
    }
    
    do {
        if(RPS()) {
            cout << 1;
            return 0;
        }
    } while(next_permutation(RPSOrder[0], RPSOrder[0] + N));
    
    cout << 0;
    return 0;
}