BOJ 15898

20 Feb 2020 • ProblemSolving

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

문제출처

문제 해석

  • 5x5격자 모양 가마에 서로 다른 재료 3개를 넣어서 만들 수 있는 최고의 폭탄 품질을 구하는 문제입니다.
  • 가마의 각 칸에는 품질을 나타내는 숫자와 원소를 나타내는 색이 칠해져 있습니다. (초기에 품질은 0, 원소는 흰색입니다)
  • 4x4 재료는 (i,j) 좌표에 2가지 정보가 있습니다.
    1. 효능 : 가마 한칸의 품질을 바꾸는 -9~9 사이의 정수
    2. 원소 : ‘R’,’B’,’G’,’Y’,’W’ 중 하나
  • 재료를 가마에 넣을 때, 범위를 벗어날 수 없고 회전이 가능합니다. 가마의 상태는 다음과 같이 바뀝니다.
    1. 재료가 위치한 가마의 격자칸에 있는 품질과 원소값이 바뀔 수 있습니다.
      • 최소 0, 최대 9를 넘지않게 재료의 효능이 더해집니다.
      • 격자의 색은 재료가 흰색이 아닌 경우, 해당 색으로 칠해집니다.
  • 재료를 3개 넣은 상태에서 폭탄의 품질은 다음과 같이 계산됩니다. 각 R,B,G,Y는 해당 색이 칠해져있는 칸의 품질의 합을 말합니다.
    • (폭탄의 품질) = 7xR + 5xB + 3xG + 2xY

설계(20)

  • 해당 문제는 백트래킹을 이용한 시뮬레이션 문제입니다.
  • 먼저, 재료를 선정해야하는데 최대 10개의 재료중 3개를 선택해야 합니다.
  • 재료를 가마에 넣으면 가마의 상태가 바뀌므로 순서가 상관이 있게 됩니다. 그러므로 O(NP3==720)이 됩니다.
  • 선택된 재료 3개를 가마에 넣을 때, 5x5가마에 4x4재료를 넣을 수 있는 위치는 총 4가지이고, 회전이 가능하므로 O(16^3)이 되므로 최악의 경우 약 O(3x10^6)가 나오게 됩니다.
  • 재료 선정을 하는 구간은 백트래킹을 이용하여 벡터에 넣을 재료를 저장하도록 하였습니다.
  • 선택된 재료의 위치와 회전 여부에 따른 재료 상태를 가마에 넣는 방식의 백트래킹을 이용하였습니다.

구현(40)

코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 5

struct info {
    int val = 0;
    char color = 'W';

};
info map[10][MAXN - 1][MAXN-1];
bool used[10];
info arr[MAXN][MAXN];
int N;
vector<int> v;
int ans = 0;
void add_map(int i_offset, int j_offset, info tmp[][MAXN - 1]) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int& val = arr[i + i_offset][j + j_offset].val;
            char& color = arr[i + i_offset][j + j_offset].color;
            char tmp_color = tmp[i][j].color;
            val += tmp[i][j].val;

            if (val < 0) val = 0;
            else if (val > 9) val = 9;
            if (tmp_color != 'W') color = tmp_color;
        }
    }
}

void rotate(info tmp_arr[][MAXN - 1]) {
    info tmp[MAXN - 1][MAXN - 1];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            tmp[4 - j - 1][i] = tmp_arr[i][j];
        }
    }
    memcpy(tmp_arr, tmp, sizeof(tmp));
}
void backtrack(int idx) {
    if (idx == 3) {
        int sum = 0;
        for (int i = 0; i < MAXN; i++) {
            for (int j = 0; j < MAXN; j++) {
                if (arr[i][j].color == 'R') {
                    sum += 7 * arr[i][j].val;
                }
                else if (arr[i][j].color == 'B') {
                    sum += 5 * arr[i][j].val;
                }
                else if (arr[i][j].color == 'G') {
                    sum += 3 * arr[i][j].val;
                }
                else if (arr[i][j].color == 'Y') {
                    sum += 2 * arr[i][j].val;
                }
            }
        }
        if (ans < sum) ans = sum;
        return;
    }
    info tmp_arr[MAXN - 1][MAXN - 1];
    memcpy(tmp_arr,map[v[idx]],sizeof(map[v[idx]]));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 4; k++) {
                if (k != 0) {
                    rotate(tmp_arr);
                }
                info tmp[MAXN][MAXN];
                memcpy(tmp,arr,sizeof(arr));
                add_map(i, j, tmp_arr);
                backtrack(idx + 1);
                memcpy(arr,tmp,sizeof(tmp));
            }
        }
    }
}
void simulate(int idx) {
    if (idx == 3) {
        backtrack(0);
        return;
    }
    for (int i = 0; i < N; i++) {
        if (used[i]) continue;
        used[i] = true;
        v.push_back(i);
        simulate(idx + 1);
        v.pop_back();
        used[i] = false;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                cin >> map[i][j][k].val;
            }
        }
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                cin >> map[i][j][k].color;
            }
        }
    }
    simulate(0);
    cout << ans << "\n";
    return 0;
}
디버깅
  • 품질과 색이 들어있는 info자료구조를 사용하는데 가마의 이전상태를 저장하기 위한 tmp배열을 복사할 때, int형으로 잘못 선언되어있어서 다른 배열들의 값도 변경이 되는 상황을 디버깅을 통해 알게 되었습니다.
  • rotate할 때 인덱싱 처리가 잘못되어 수정하였습니다.
제출결과
  • 660ms

마무리

  • 백트래킹을 이용한 시뮬레이션 문제였습니다. 삼성역량테스트가 해당문제와 같이 복잡한 시뮬레이션 문제를 내는 경향이 강합니다. 역량테스트용으로 연습하기 아주 좋은 문제인 것 같습니다.
  • 제한시간이 3초라 넉넉하긴 하지만 660ms라는 만족스럽지 않은 제출결과가 나왔습니다. 이유는 백트래킹을 실행할 때마다 가마에 넣고, 이전 가마의 상태를 저장해 놓기 위해 tmp배열을 별도로 선언한 부분에 의해 제출결과가 느리게 나온 것 같습니다.
 BOJ

Related Posts