BOJ 1657 두부장수 장홍준

1 개요

BOJ 1657 두부장수 장홍준

• 백준 온라인 저지 1657번 문제
• BOJ 47단계

2 C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 14;
int N, M;
int tile[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}
};
char grid[MAX][MAX];
int dp[MAX][MAX][2 << MAX];

int dfs(int row, int col, int filled) {
    if (row == N) return 0;
    if (col == M) return dfs(row + 1, 0, filled);

    int &ret = dp[row][col][filled];
    if (ret != -1) return ret;

    if (filled & (1 << col))
        return ret = dfs(row, col + 1, filled & ~(1 << col));

    ret = dfs(row, col + 1, filled);
    if (row <= N - 2)
        ret = max(ret, dfs(row, col + 1, filled | (1 << col)) + tile[grid[row][col]][grid[row + 1][col]]);
    if (col <= M - 2 && !(filled & (2 << col)))
        ret = max(ret, dfs(row, col + 2, filled) + tile[grid[row][col]][grid[row][col + 1]]);
    return ret;
}

void solve() {
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 0, 0);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    char c;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> c;
            if (c == 'F') grid[i][j] = 4;
            else grid[i][j] = c - 'A';
        }
    }
    solve();
}