[BOJ / 브루트포스] 15898 피아의 아틀리에 ~신비한 대회의 연금술사~

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

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

 

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

알고리즘 : 구현 / 브루트포스

문제 티어 : 골드 I

UCPC 2018 예선 문제 중 하나인 문제이다.

배열돌리기와 순열을 이용한 간단한 구현 문제이다.. 그러나 배열돌리기를 다른데서 퍼왔다가 잘못된 코드인 바람에 디버깅이 오래걸렸다. (설마 여기서 났겠어 했다가.. ㅋㅋ) 골드1치고는 되게 쉬운 문제인 것 같다. 

총 10P3 * 4^3 * 4^3 * 16 정도 시간이 소요되는 것 같아서 다 돌렸는데, 각 상황(rotation, 시작위치)을 하나의 변수로 놓기에는 계산하기 귀찮아질 것이 뻔해서 rotation이 4가지 경우, 시작위치가 4가지 경우, 재료가 총 10개이므로 백의 자리 수 하나로 만들어 관리하였다.

 

- 백의 자리(1~4) : 시작위치 - map으로 관리해서 어느 위치에 재료를 놓을 것인지 정한다

- 십의 자리(1~4) : rotation 횟수 - 몇 번 회전할지 정한다

- 일의 자리(0~9) : 재료 인덱스 

 

 

 

< CODE >

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int n;

vector<int> v;
map<int, pair<int, int>> m;
map<char, int> rgb;

int power[10][4][4];
char color[10][4][4];

int tPower[2][4][4];
char tColor[2][4][4];

int pBoard[5][5];
char cBoard[5][5];

bool use[10];

int result;

void rotate(int idx, int deg) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			tPower[0][i][j] = power[idx][i][j];
			tColor[0][i][j] = color[idx][i][j];
		}
	}

	bool cur = false;

	while (deg--) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				tPower[!cur][i][j] = tPower[cur][3 - j][i];
				tColor[!cur][i][j] = tColor[cur][3 - j][i];
			}
		}

		cur = !cur;
	}
}

void solve() {
	for (int k = 0; k < 3; k++) {
		int value = v[k];
		int idx = value % 10; value /= 10;
		int deg = value % 10; value /= 10;
		pair<int,int> sPos = m[value];
		
		deg -= 1;

		rotate(idx, deg);
		
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				int y = i + sPos.first;
				int x = j + sPos.second;

				pBoard[y][x] += tPower[deg%2][i][j];

				if (pBoard[y][x] < 0)
					pBoard[y][x] = 0;
				else if (pBoard[y][x] > 9)
					pBoard[y][x] = 9;
				
				if (tColor[deg % 2][i][j] != 'W')
					cBoard[y][x] = tColor[deg % 2][i][j];
			}
		}
	}

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			if(cBoard[i][j] != 'W')
				rgb[cBoard[i][j]] += pBoard[i][j];

			pBoard[i][j] = 0;
			cBoard[i][j] = 'W';
		}
	}

	result = max(result, 7 * rgb['R'] + 5 * rgb['B'] + 3 * rgb['G'] + 2 * rgb['Y']);

	rgb['R'] = 0; rgb['B'] = 0;
	rgb['G'] = 0; rgb['Y'] = 0;
}

void com(int amount) {
	if (amount == 3) {
		solve();
		return;
	}

	for (int k = 0; k < n; k++) {
		if (!use[k]) {
			use[k] = true;
			for (int i = 1; i <= 4; i++) {
				for (int j = 1; j <= 4; j++) {
					int num = i * 100 + j * 10 + k;
					v.push_back(num);
					com(amount + 1);
					v.pop_back();
				}
			}
			use[k] = false;
		}
	}
}

void init() {
	cin >> n;

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				cin >> power[k][i][j];
			}
		}

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				cin >> color[k][i][j];
			}
		}
	}

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			pBoard[i][j] = 0;
			cBoard[i][j] = 'W';
		}
	}

	m[1] = { 0,0 }; m[2] = { 0,1 };
	m[3] = { 1,0 }; m[4] = { 1,1 };
}

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

	init();
	com(0);

	cout << result << '\n';

	return 0;
}

시간 : 1476ms

 

태그 : #백준 15898 #UCPC 2018 #UCPC 15898 #UCPC 피아체 #BOJ 15898