16986 인싸들의 가위바위보

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

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

인싸들은 가위바위보도 신기하게 하네요... 

문제의 수 범위가 좁아서 백트래킹으로 지우가 낼 손동작을 모두 만들어놓고 시뮬레이션을 하면 될 것 같았는데 막상 구현하려니 어떻게 해야 할지 모르겠어서 블로그를 참고했다.

 

https://velog.io/@front/백준-인싸들의-가위바위보-16986

이분이 짜신 코드 정말 완벽하다고 느꼈다 👍 👍

 

한 경기가 끝나고 다음 사람의 경기는 어떻게 처리할지 생각을 많이 했었는데 go함수를 만들고 3-p1-p2 이런 식으로 코드를 짜주면 간단하게 처리가 가능했다.

#include <bits/stdc++.h>
using namespace std;
//0 지우
//1 경희
//2 민호

int n,k,ans;
int rsp[13][13]; //가위바위보 상성
int pattern[23][3]; //경기에서 낼 손동작 순서, 사람
int ptr[3]; //각 사람의 현재 경기 수
int scores[3]; //각 사람의 승점 
bool isused[13];

void go(int p1, int p2){
    if(scores[0]>=k) {ans=1; return;}
    if(scores[1]>=k || scores[2]>=k) return;
    if(ptr[0]>n) return;
    if(p1>p2) swap(p1,p2);
    //p1이 이기면
    if(rsp[pattern[ptr[p1]++][p1]][pattern[ptr[p2]++][p2]]==2){
        scores[p1]++;
        go(p1,3-p1-p2);
    }
    //p1이 지거나 비기면
    else{
        scores[p2]++;
        go(p2,3-p1-p2);
    }
}

void func(int k){
    if(ans) return; //종료조건

    if(k==n){
        go(0,1); //지우와 경희가 처음에 경기함
        ptr[0]=ptr[1]=ptr[2]=0;
        scores[0]=scores[1]=scores[2]=0;
        return;
    }

    for(int i=1;i<=n;i++){ //손동작은 종류가 1~n까지
        if(ans) return; //종료조건
        if(!isused[i]){
            isused[i]=true;
            pattern[k][0]=i;
            func(k+1);
            isused[i]=false;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    
    if(k>n) {cout<<0; return 0;}

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>rsp[i][j];

    for(int i=1;i<=2;i++) //경희와 민호만 입력받음
        for(int j=0;j<20;j++)
            cin>>pattern[j][i];

    func(0);
    cout<<ans;
    return 0;
}