발상
두부 조합에 따라 두부 한 모의 가치가 달라진다. 한 모는 2개의 두부 조각으로 이루어지므로 2차 배열에 모든 두부의 가치를 미리 저장하면 두부 한 모를 완성했을 때의 가치를 바로 알 수 있다. 다음으로 할 것은 두부판을 최적으로 쪼개는 일이다. 두부판을 우상단 방향으로 탐색할 때 각 두부 조각에 취할 수 있는 선택지는 아래 3가지다.
- 오른쪽 두부 조각과 합친다.
- 위쪽 두부 조각과 합친다.
- 현재 두부 조각을 버린다.
문제는 현재 조각이 아래쪽 조각과 이미 합쳐진 상태인지 판별하는 부분이다. ( 왼쪽과 합쳐진 조각일 경우 인덱스를 +1이 아니라 +2하는 것으로 탐색 자체를 생략할 수 있다. )
먄약 이미 합쳐진 조각이라면 저 세가지 선택지는 모두 의미가 없다.
따라서 두부 조각을 합칠 때 마다 위쪽 조각과 합쳐졌는지 저장할 필요가 있다.
위쪽 조각과 합쳤을 때 이후 탐색에 영향을 미칠 수 있는 위치는 아래 그림과 같다.
파란색 원의 위치까지 탐색했을 때 빨간색 마름모 위치는 위쪽 조각과 합쳤을 때, 다음 탐색에 영향을 미칠 수 있는 영역이다.
반대로 X에 해당하는 영역들은 위쪽과 합치든 말든 영향이 없다.
따라서 우리가 해야 할 일은 저 마름모에 해당하는 영역의 조합 여부를 비트마스크로 저장하며 탐색하는 일이다.
비트마스크를 통해 현재 조각이 이미 합쳐진 조각인지를 판별한 뒤 처음 제시한 3가지 선택지 중 가장 가치가 커지는 조합을 골라나가면 답을 구할 수 있다.
점화식
코드
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
const int val[5][5] = {
{10, 8, 7, 5, 1},
{8, 6, 4, 3, 1},
{7, 4, 3, 2, 1},
{5, 3, 2, 2, 1},
{1, 1, 1, 1, 0},
};
int n, m; vector<vector<int>> arr, dp;
int r(int pos, int st) {
if (pos > n * m) return 0;
int& ret = dp[pos][st];
if (ret != -1) return ret;
ret = r(pos + 1, st / 2); // 현재 조각을 버리는 경우
if ((st & 1) == 0) { // 현재 위치 조각이 합쳐지지 않은 조각인 경우
int x = ((pos - 1) / m) + 1;
int y = ((pos - 1) % m) + 1;
int s1 = 0, s2 = 0;
if (x < n) { // 세로로 합치려면 마지막 줄이 아니어야 함
s1 = r(pos + 1, (st >> 1) | (1 << (m - 1))) + val[arr[x][y]][arr[x + 1][y]]; // 세로로 합친 경우
}
if (y < m && (st & 2) == 0) { // 가로로 합치려면 다음 조각도 합쳐지지 않은 조각이어야 함
s2 = r(pos + 2, st / 4) + val[arr[x][y]][arr[x][y + 1]]; // 가로로 합친 경우
}
ret = max({ ret, s1, s2 });
}
return ret;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m; arr = vector<vector<int>>(n + 1, vector<int>(m + 1)); dp = vector<vector<int>>(n * m + 1, vector<int>(1 << m, -1));
for (int i = 1; i <= n; i++) {
string s; cin >> s;
for (int j = 1; j <= m; j++) {
arr[i][j] = s[j - 1] - 'A';
if (arr[i][j] == 5) arr[i][j]--;
}
}
cout << r(1, 0);
return 0;
}