문제 설명
5x5 격자 모양 가마에 N 개의 재료 중 서로 다른 재료 3개를 넣고 최대 품질의 폭탄을 만드는 문제입니다.
풀이
재료의 크기가 4x4라서 가마에 넣을 때
이렇게 4가지 방법으로 넣을 수 있고
저 방법에서 재료들을 회전해서 넣을 수 있어 한 재료를 넣을 때 총 4 x 4 = 16가지 방법으로 넣을 수 있습니다.
N 개의 재료 중 3개를 선택하여 각각 16가지 방법으로 배치하면 모든 경우를 볼 수 있습니다.
완전 탐색을 해도 N이 최대 10이므로 10 * 9 * 8 * 16^3 = 2,949,120이라 시간이 충분합니다.
재료 3개를 넣으면서 가마의 효능과 원소는 문제를 참고하여 계산해야 합니다.
가마에 재료 3개를 넣은 효능과 원소가 구해졌으면 문제에서 주어진 폭탄의 품질을 계산하는 식으로 계산하면 됩니다.
재료 계산하는 과정이 3 * 4 * 4이므로 총 시간 복잡도는 O(n^3 * 16^3 * 48) ≒ 2,949,120 * 48 = 141,557,760입니다.
3초 안에 충분히 돌아가겠네요.
완전 탐색을 하여 모든 경우를 다 계산하고 최댓값을 구하는 방법은 생각하기 쉽지만
구현이 복잡한 문제입니다.
문제 푸는데 시간이 좀 걸려서 구현 문제도 많이 풀어봐야겠네요…
소스 코드
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pic pair <int,char>
#define fs first
#define sd second
using namespace std;
int main() {
FIO;
int n, ans = 0; cin >> n;
pic rot[10][4][5][5]; // first = 효능, second = 원소
FOR(i, 0, n - 1) {
FOR(j, 0, 3) FOR(k, 0, 3)
cin >> rot[i][0][j][k].fs;
FOR(j, 0, 3) FOR(k, 0, 3)
cin >> rot[i][0][j][k].sd;
FOR(r, 0, 2) FOR(j, 0, 3) FOR(k, 0, 3) // rotate
rot[i][r + 1][k][3 - j] = { rot[i][r][j][k].fs,rot[i][r][j][k].sd };
}
tuple <int, int, int, int> arr[3];
bool visit[10] = {};
int chk[26];
chk['W' - 'A'] = 0, chk['R' - 'A'] = 7, chk['B' - 'A'] = 5;
chk['G' - 'A'] = 3, chk['Y' - 'A'] = 2;
function <void(int)> per = [&](int lv) {
if (lv == 3) {
pic map[5][5];
FOR(i, 0, 4) FOR(j, 0, 4)
map[i][j] = { 0, 'W' };
FOR(i, 0, 2) FOR(j, 0, 3) FOR(k, 0, 3) { // 재료 계산
int d, r, y, x;
tie(d, r, y, x) = arr[i];
y += j, x += k;
pic& a = map[y][x], & b = rot[d][r][j][k];
if (b.sd != 'W') a.sd = b.sd;
a.fs += b.fs;
if (a.fs < 0) a.fs = 0;
if (a.fs > 9) a.fs = 9;
}
int sum = 0;
FOR(i, 0, 4) FOR(j, 0, 4) // 품질 계산
sum += chk[map[i][j].sd - 'A'] * map[i][j].fs;
ans = max(ans, sum);
return;
}
FOR(i, 0, n - 1) {
if (visit[i]) continue;
visit[i] = 1;
FOR(j, 0, 1) FOR(k, 0, 1) FOR(r, 0, 3) {
arr[lv] = { i,r,j,k };
per(lv + 1);
}
visit[i] = 0;
}
};
per(0);
cout << ans << '\n';
return 0;
}