[백준/BOJ] 백준 1079번 : 마피아

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

1079번: 마피아

 

게임에서 한 명씩 지워가는 경우를 모두 고려하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int player_num;
int r[16][16];
int player;

int Solve(int player_num, int night_cnt, vector<int> cost, vector<int> erased)
{
	int ret = -1;

	//참가자가 짝수명일때 (밤일때)
	if (player_num % 2 == 0)
	{
		//지워지지 않은 사람들중 하나를 지운다
		for (int i = 0; i < erased.size(); i++)
		{
			if (erased[i] == 1)
				continue;
			if (i == player) //자기 자신일때
				continue;

			//i번 플레이어를 지울때
			erased[i] = 1;
			for (int j = 0; j < cost.size(); j++)
			{
				cost[j] += r[i][j];
			}
			ret = max(ret, Solve(player_num - 1, night_cnt + 1, cost, erased));

			//i번 플레이어를 지운것 원상복구
			for (int j = 0; j < cost.size(); j++)
			{
				cost[j] -= r[i][j];
			}
			erased[i] = 0;
		}
	}

	//참가자가 홀수명일때 (낮일때)
	else
	{
		int erase_index = -1;
		int cost_max = -1;

		//유죄 지수가 가장 높은 사람을 지운다
		for (int i = 0; i < cost.size(); i++)
		{
			//이미 지워진 사람일때
			if (erased[i] == 1)
				continue;

			//더 큰 유죄 지수를 찾았을때
			if (cost_max < cost[i])
			{
				erase_index = i;
				cost_max = cost[i];
			}
		}

		//지워진 사람이 플레이어일때
		if (erase_index == player)
			return night_cnt;

		erased[erase_index] = 1; //해당 플레이어가 지워진것을 체크한다
		ret = Solve(player_num - 1, night_cnt, cost, erased);
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	vector<int> cost;
	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		cost.push_back(input);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int input;
			cin >> input;

			r[i][j] = input;
		}
	}
	cin >> player;

	vector<int> erased(n, 0);
	cout << Solve(n, 0, cost, erased);

	return 0;
}