[BOJ 8896] 가위 바위 보

 2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8896에서 채점할 수 있습니다.

요약 )

 N개의 로봇이 모두 모여 가위 바위 보를 하는 문제입니다. 각 로봇이 R, S, P 중 무엇을 낼지 정해져 있으므로, 가위 바위 보를 통해 로봇이 탈락하고 살아남는 과정을 그대로 구현하면 됩니다. 여기에서는 아래와 같은 배열 alive 를 관리하면서 구현하였습니다.

alive[i] = i번째 로봇이 아직 살아있는가? 살아있으면 yes, 탈락했으면 no

초기화 )

// code by RiKang, weeklyps.com
scanf("%d",&n);
for(int i=1; i<=n; i++){
    cin>>s[i];
    alive[i] = true;
}

 먼저 초기화 부분에선 모든 로봇이 살아있도록 설정합니다.

가위 바위 보 k번 시행 )

// code by RiKang, weeklyps.com
k = s[1].size();
for(int i=0; i<k; i++){
    // R, S, P 중 진 패가 무엇인지를 알아냄.
    // 진 패를 낸 로봇을 탈락시킴.
}

 그 다음엔 가위 바위 보를 k번 시행해야 합니다. 가위 바위 보를 할 때마다, 가위 바위 보 중 무엇이 졌는지를 확인한 다음 해당하는 로봇들을 탈락시켜 나가면 최후에 어떤 로봇이 살아남았는지를 알 수 있을 것입니다.

가위 바위 보 중 무엇이 졌는지 알아내기 )

// code by RiKang, weeklyps.com
k = s[1].size();
for(int i=0; i<k; i++){
    for(int j=0; j<3; j++) rsp[j]=0;
    for(int j=1; j<=n; j++){
        if(!alive[j]) continue;
        if(s[j][i]=='R') rsp[0]=1;
        else if(s[j][i]=='S') rsp[1]=1;
        else if(s[j][i]=='P') rsp[2]=1;
    }
    if(rsp[0]+rsp[1]+rsp[2]==2){
        char lose_char;
        if(rsp[0]==0) lose_char = 'P'; // S vs P
        else if(rsp[1]==0) lose_char = 'R'; // P vs R
        else if(rsp[2]==0) lose_char = 'S'; // R vs S
    }
}

 아직 살아있는 로봇 중, R을 낸 로봇이 있으면 rsp[0] = 1, S를 낸 로봇이 있으면 rsp[1] = 1, P를 낸 로봇이 있으면 rsp[2]=1로 설정하였습니다. 그러면 rsp[0]+rsp[1]+rsp[2] 가 1인 경우, 2인 경우, 3인 경우를 생각해 볼 수 있습니다.

 가위 바위 보 룰을 생각해 보면 rsp[0]+rsp[1]+rsp[2] = 1인 경우는 모두 다 같은 것을 낸 경우이기 때문에 무승부입니다. rsp[0]+rsp[1]+rsp[2] = 3인 경우는 가위 바위 보 세가지가 모두 등장하여 무승부인 경우입니다. 따라서 rsp[0]+rsp[1]+rsp[2] = 2인 경우에만 탈락자가 존재합니다.

 탈락해야 하는 것이 R, S, P 중 무엇인지는 위의 코드와 같이 찾을 수 있습니다. 예를 들어, rsp[0]==0 이라면 R이 하나도 없다는 뜻이고, 결국 S(가위) vs P(보) 가 붙은 것이기 때문에 보가 탈락하게 됩니다.

로봇 탈락시키기 )

// code by RiKang, weeklyps.com
k = s[1].size();
for(int i=0; i<k; i++){
    for(int j=0; j<3; j++) rsp[j]=0;
    for(int j=1; j<=n; j++){
        if(!alive[j]) continue;
        if(s[j][i]=='R') rsp[0]=1;
        else if(s[j][i]=='S') rsp[1]=1;
        else if(s[j][i]=='P') rsp[2]=1;
    }
    if(rsp[0]+rsp[1]+rsp[2]==2){
        char lose_char;
        if(rsp[0]==0) lose_char = 'P'; // S vs P
        else if(rsp[1]==0) lose_char = 'R'; // P vs R
        else if(rsp[2]==0) lose_char = 'S'; // R vs S    // 진 패를 낸 로봇을 탈락시킴.
        for(int j=1; j<=n; j++)
            if(s[j][i]==lose_char)
                alive[j] = false;
    }
}

 무엇이 졌는지를 lose_char에 저장했기 때문에 lose_char를 낸 로봇들을 alive[j]=false 로 탈락시킵니다. 

정답 출력하기 )

// code by RiKang, weeklyps.com
int cnt=0, ans=0;
for(int i=1; i<=n; i++){
    if(alive[i]){
        cnt++;
        ans=i;
    }
}
if(cnt!=1) ans=0;
printf("%d\n",ans);

 살아남은 로봇이 하나라면 그 로봇의 번호를, 아니라면 0을 출력합니다.

최종 코드 )

// code by RiKang, weeklyps.com
// 2012 ACM-ICPC Daejeon regional - I
// BOJ 8896 가위 바위 보
// O(K*N) solution
 
#include <bits/stdc++.h>
using namespace::std;
 
int n,k;
string s[35];
bool alive[15]; // alive[i] = i가 아직 살아있나?
int rsp[4];
 
void solve(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        cin>>s[i];
        alive[i] = true;
    }
    k = s[1].size();
    
    for(int i=0; i<k; i++){
        for(int j=0; j<3; j++) rsp[j]=0;
        for(int j=1; j<=n; j++){
            if(!alive[j]) continue;
            if(s[j][i]=='R') rsp[0]=1;
            else if(s[j][i]=='S') rsp[1]=1;
            else if(s[j][i]=='P') rsp[2]=1;
        }
        if(rsp[0]+rsp[1]+rsp[2]==2){
            char lose_char;
            if(rsp[0]==0) lose_char = 'P'; // S vs P
            else if(rsp[1]==0) lose_char = 'R'; // P vs R
            else if(rsp[2]==0) lose_char = 'S'; // R vs S
            for(int j=1; j<=n; j++)
                if(s[j][i]==lose_char)
                    alive[j] = false;
        }
    }
    int cnt=0, ans=0;
    for(int i=1; i<=n; i++){
        if(alive[i]){
            cnt++;
            ans=i;
        }
    }
    if(cnt!=1) ans=0;
    printf("%d\n",ans);
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}