[백준/BOJ] 백준 15898번 : 피아의 아틀리에 ~신비한 대회의 연금술사~

www.acmicpc.net/problem/15898

15898번: 피아의 아틀리에 ~신비한 대회의 연금술사~

재료 3개를 고르고 그 재료 3개의 순서를 결정해서 문제를 해결했다. 재료와 순서를 결정했을 때 각 재료가 회전했을 때를 고려하고, 다시 돌아올 때는 저장해놓은 원본 보드를 이용했다.

 

코드

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

int n;
pair<int, char> board[5][5];
pair<int, char> material[10][4][4];
int result = -987654321;

void Pre()
{
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
		{
			board[i][j].first = 0;
			board[i][j].second = 'W';
		}
}

//점수 계산
int Check()
{
	int r = 0;
	int b = 0;
	int g = 0;
	int y = 0;

	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
		{
			if (board[i][j].second == 'R')
				r += board[i][j].first;

			else if (board[i][j].second == 'B')
				b += board[i][j].first;

			else if (board[i][j].second == 'G')
				g += board[i][j].first;

			else if (board[i][j].second == 'Y')
				y += board[i][j].first;
		}

	return (7 * r) + (5 * b) + (3 * g) + (2 * y);
}

//here를 기준으로 재료를 넣는다
void Set(pair<int, int> here, int material_number)
{
	for (int i = here.first; i < here.first + 4; i++)
		for (int j = here.second; j < here.second + 4; j++)
		{
			pair<int, char> here_board = board[i][j];

			here_board.first += material[material_number][i - here.first][j - here.second].first;

			if (here_board.first < 0)
				here_board.first = 0;
			else if (here_board.first > 9)
				here_board.first = 9;

			if (material[material_number][i - here.first][j - here.second].second != 'W')
				here_board.second = material[material_number][i - here.first][j - here.second].second;

			board[i][j] = here_board;
		}
}

//회전
void Turn(int material_number)
{
	pair<int, char> new_material[4][4];

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
		{
			new_material[i][j] = material[material_number][3 - j][i];
		}

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
		{
			material[material_number][i][j] = new_material[i][j];
		}
}

void Make(vector<int> select, int index)
{
	//다 고려 했을때
	if (index == 3)
	{
		result = max(result, Check());
		return;
	}

	pair<int, char> original_board[5][5];

	//원본 보드를 저장
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			original_board[i][j] = board[i][j];

	for (int t = 0; t < 4; t++)
	{
		//(0,0), (0,1), (1,0), (1,1)을 기준으로 재료를 넣는것을 고려한다
		Set(make_pair(0, 0), select[index]);
		Make(select, index + 1);
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				board[i][j] = original_board[i][j]; //되돌리기

		Set(make_pair(0, 1), select[index]);
		Make(select, index + 1);
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				board[i][j] = original_board[i][j];

		Set(make_pair(1, 0), select[index]);
		Make(select, index + 1);
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				board[i][j] = original_board[i][j];

		Set(make_pair(1, 1), select[index]);
		Make(select, index + 1);
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				board[i][j] = original_board[i][j];

		//해당 보드를 돌린다
		Turn(select[index]);
	}
}

void Solve()
{
	vector<int> perm;

	for (int i = 0; i < n; i++)
		perm.push_back(0);

	//n개중 3개를 고르는것이므로 3개에 체크한다
	perm[0] = 1;
	perm[1] = 1;
	perm[2] = 1;

	sort(perm.begin(), perm.end());

	do {

		vector<int> select;
		for (int i = 0; i < perm.size(); i++)
		{
			if (perm[i] == 1) //고를 재료 선택
				select.push_back(i);
		}

		//고른 재료의 순서 결정
		sort(select.begin(), select.end());
		do
		{
			Make(select, 0); //결정한 순서대로 재료 넣기
		} while (next_permutation(select.begin(), select.end()));

	} while (next_permutation(perm.begin(), perm.end()));
}

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

	Pre();

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		//효능
		for (int j = 0; j < 4; j++)
			for (int k = 0; k < 4; k++)
			{
				int input;
				cin >> input;

				material[i][j][k].first = input;
			}

		//원소
		for (int j = 0; j < 4; j++)
			for (int k = 0; k < 4; k++)
			{
				char input;
				cin >> input;

				material[i][j][k].second = input;
			}
	}

	Solve();

	cout << result;

	return 0;
}