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

www.acmicpc.net/problem/16986

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

낼 수 있는 손동작이 총 9개 이므로 브루트포스를 사용해서 모든 경우의 수를 확인하는 문제이다.

지우가 모든 손동작을 다르게 내어 우승할 수 있으면 1을, 그렇지 않으면 0을 출력한다.

 

지우가 내는 손동작이 모두 달라야 하므로 순열을 사용했다.

 

next_permutation(배열 혹은 벡터의 시작점, 배열 혹은 벡터의 마지막 점)

순열을 구한 후 다음 순열이 존재하면 true 그렇지 않으면 false를 리턴한다.

#include <algorithm>

next_permutaion(arr,arr+n)

 

문제에서 잘못 이해한 점이 있었는데 공통된 round 순서대로 내는 게 아니라 각 사람마다 round가 다르다는 점이었다.

따라서 rount를 체크할 cnt 배열이 필요했다.

 

지우를 0, 경희를 1, 민호를 2로 둔다.

우승자 로직

rsp[i][j]는 i 사람이 j번째 내는 손동작을 의미한다.

따라서 rsp[p1][cnt[p1]]은 p1이 cnt[p1]번쨰 내는 손동작이다.

 

arr[i][j]는 손동작 i와 j사이의 상성을 보여준다.

2이면 i가 j를 이김

1이면 비김 -> 1일 경우 뒤에 사람이 이기므로 둘 중 max값을 리턴한다.

0이면 i가 j한테 짐

 

  do
  {
    score[0] = score[1] = score[2] = 0;
    cnt[0] = cnt[1] = cnt[2] = 1;
    if (dfs(0, 1) == 0)
    {
      printf("1");
      return 0;
    }
  } while (next_permutation(rsp[0] + 1, rsp[0] + n + 1));

지우의 순열을 구한 후 매번 score와 cnt를 초기화해줘야 한다.

해당 수열에 승자가 0(지우)가 나온다면 1을 리턴하고 함수를 종료한다.

 

 

//인싸들의 가위바위보
//블로그에 아직 안적음
#include <stdio.h>
#include <algorithm>

using namespace std;
int arr[10][10];
int rsp[3][21];
int n, k;
int score[3], cnt[3];

int whoIsWinner(int p1, int p2)
{
  int res = arr[rsp[p1][cnt[p1]++]][rsp[p2][cnt[p2]++]];
  if (res == 2)
    return p1;
  else if (res == 0)
    return p2;
  else
    return max(p1, p2);
}

int nextPlayer(int p1, int p2)
{
  return (3 - (p1 + p2));
}

int dfs(int p1, int p2)
{
  if (cnt[0] > n)
  {
    return -1;
  }

  int winner = whoIsWinner(p1, p2);
  score[winner]++;
  if (score[winner] == k)
    return winner;
  return dfs(nextPlayer(p1, p2), winner);
}
int main(void)
{

  scanf("%d%d", &n, &k);

  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      scanf("%d", &arr[i][j]);
    }
  }

  for (int i = 1; i <= 20; i++)
    scanf("%d", &rsp[1][i]);
  for (int i = 1; i <= 20; i++)
    scanf("%d", &rsp[2][i]);

  for (int i = 1; i <= n; i++)
  {
    rsp[0][i] = i;
  }
  do
  {
    score[0] = score[1] = score[2] = 0;
    cnt[0] = cnt[1] = cnt[2] = 1;
    if (dfs(0, 1) == 0)
    {
      printf("1");
      return 0;
    }
  } while (next_permutation(rsp[0] + 1, rsp[0] + n + 1));

  printf("0");
  return 0;
}