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

작성일 | In

문제 링크

  • http://icpc.me/16986

문제 출처

  • 2019 3/1 코딩테스트 특강 ( /Ba+rking/님 )

사용 알고리즘

  • BFS
  • Brute Force

풀이

3/1에 서울대학교에서 진행된 코딩테스트 특강 모의고사 문제입니다.

이 문제는 2개의 부분 문제로 나누어 풀 수 있습니다.

  1. 지우가 낼 순서 정하기
  2. 시뮬레이션 돌리기

1. 순서 정하기

지우는 1부터 N까지 N개의 수를 한 번씩 사용할 수 있습니다. 배열에 1부터 N까지 차례대로 저장하고, permutation을 돌리면 지우가 낼 순서를 모두 구할 수 있습니다.
이 작업은 O(N!)이 걸리고, N은 최대 9이므로 약 360,000개 정도의 순열에 대해 시뮬레이션을 돌리면 됩니다.

문제 하단에 나와있지만, 다른 플레이어가 앞으로 낼 손동작을 20개만 예측해도 전혀 문제가 없습니다.
Lemma 1. 각 플레이어가 앞으로 20경기에서 낼 손동작만 미리 알고 있어도 지우가 우승할 수 있는지 예측하는데 문제가 없다.
proof ) 비둘기집의 원리에 의해 3(K-1)+1, 즉 3K-2번 게임을 하면 우승자가 결정이 되는데, K는 최대 6이므로 20번의 게임만으로 우승 여부를 확정지을 수 있다.

2. 시뮬레이션 돌리기

지우가 낼 순서를 arr[1][1…N], 경희와 민호가 낼 순서를 각각 arr[2][1…20], arr[3][1…20]에 저장을 했다고 가정합시다.
지우, 경희, 민호가 몇 번째 인덱스에 저장된 손동작을 낼지 기억하는 idx배열과 몇 번 이겼는지 기억하는 win배열을 만들면 편하게 구현할 수 있습니다.
구현이 까다롭지는 않은 것으로 생각되어 설명은 코드로 대체하도록 하겠습니다. 시뮬레이션의 구현은 f() 함수 부분을 보시면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

int n, k;
int vs[10][10];

int arr[4][21];

bool f(){
	int idx[4] = {0, 1, 1, 1};
	int win[4] = {0, 0, 0, 0};

	int p1 = 1, p2 = 2, p3 = 3; //p3은 참가 x

	while(1){
		if(p1 > p2) swap(p1, p2);

		if(p1 == 1 && idx[1] > n) break;
		if(idx[p1] > 20 || idx[p2] > 20) break;
		int a = arr[p1][idx[p1]++];
		int b = arr[p2][idx[p2]++];

		if(vs[a][b] == 2){
			win[p1]++; swap(p2, p3);
			if(win[p1] == k) break;
		}else{
			win[p2]++; swap(p1, p3);
			if(win[p2] == k) break;
		}
	}

	return win[1] >= k;
}

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 >> vs[i][j];
		}
	}

	for(int i=1; i<=20; i++) cin >> arr[2][i];
	for(int i=1; i<=20; i++) cin >> arr[3][i];
	for(int i=1; i<=n; i++) arr[1][i] = i;

	do{
		if(f()){
			cout << 1; return 0;
		}
	}while(next_permutation(arr[1]+1, arr[1]+n+1));
	cout << 0;
}