Solution
1. 참가자가 1명이 남고 그 사람이 시민일 경우, 2. 참가자가 1명이 남고 그 사람이 은진이일 경우
이다Brute Force
문제DFS
DFS 함수의 파라미터로는 현재 남은 player의 수 (pnum)
과 몇 번의 밤이 지나갔는지 체크하는 (day)
기저조건은 참가자가 1명이 남았을 경우에 그 사람이 시민일 경우와 은진이일 경우로 나누어질 수 있다 (즉 은진이가 죽거나 남은 player가 1명일 경우로 표현 가능)
if (pnum == 1 || alive[jin] == false) {
if (day > ret) ret = day;
return;
}
밤 (pnum%2==0)
: 마피아가 죽일 사람을 고름 (은진이는 죽을 수 없음)
i
를 죽였을 경우 다른 참가자 유죄지수를 R[i][]
만큼 변경해줌 dfs (pnum-1, day+1)
: 사람을 1명 줄이고 밤을 추가해주어 dfs 호출 //night
if (pnum % 2 == 0) {
for (int i = 0; i < N; i++) {
if (alive[i] == false || i==jin) continue;
alive[i] = false;
for (int j = 0; j < N; j++) {
if (alive[j] == false) continue;
score[j] += guilty[i][j];
}
dfs(pnum - 1, day + 1);
for (int j = 0; j < N; j++) {
if (alive[j] == false) continue;
score[j] -= guilty[i][j];
}
alive[i] = true;
}
}
낮 (pnum%2!=0)
: 유죄지수가 가장 높은 사람을 죽임 (은진이가 죽을 수도 있음)dfs (pnum-1, day)
: 사람을 1명 죽이지만 낮이므로 밤을 추가해주진 않음 //day
else {
int max_score = 0;
int kill=0;
for (int i = 0; i < N; i++) {
if (alive[i] == false) continue;
if (max_score < score[i]) {
max_score = score[i];
kill = i;
}
}
if (kill == jin) {
if (ret < day) ret = day;
return;
}
alive[kill] = false;
dfs(pnum - 1, day);
alive[kill] = true;
}
Source Code
#include <iostream>
#include <vector>
const int MAX = 17;
using namespace std;
int ret=0;
int N;
int jin;
int score[MAX];
bool alive[MAX];
int guilty[MAX][MAX];
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> score[i];
alive[i] = true;
}
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> guilty[i][j];
cin >> jin;
}
void dfs(int pnum, int day) {
//은진이가 죽거나 남아있는 player가 1명일 때
if (pnum == 1 || alive[jin] == false) {
if (day > ret) ret = day;
return;
}
//night
if (pnum % 2 == 0) {
for (int i = 0; i < N; i++) {
if (alive[i] == false || i==jin) continue;
alive[i] = false;
for (int j = 0; j < N; j++) {
if (alive[j] == false) continue;
score[j] += guilty[i][j];
}
dfs(pnum - 1, day + 1);
for (int j = 0; j < N; j++) {
if (alive[j] == false) continue;
score[j] -= guilty[i][j];
}
alive[i] = true;
}
}
//day
else {
int max_score = 0;
int kill=0;
for (int i = 0; i < N; i++) {
if (alive[i] == false) continue;
if (max_score < score[i]) {
max_score = score[i];
kill = i;
}
}
if (kill == jin) {
if (ret < day) ret = day;
return;
}
alive[kill] = false;
dfs(pnum - 1, day);
alive[kill] = true;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
input();
dfs(N, 0);
cout << ret << endl;
return 0;
}