BOJ 2169 로봇 조종하기

1 개요

BOJ 2169 로봇 조종하기

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

2 C++

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

const int MAX_N = 1000;
int n, m;
int memo[MAX_N + 1][MAX_N + 1][3], cost[MAX_N + 1][MAX_N + 1];

int dp(int x, int y, int dir) {
    if (x < 1 || x > n || y < 1 || y > m) return -1e9;
    if (x == n && y == m) return cost[x][y];
    
    int &ret = memo[x][y][dir];
    if (ret != -1) return ret;
    
    if (dir == 0) ret = max({dp(x + 1, y, 0), dp(x, y - 1, 1), dp(x, y + 1, 2)}) + cost[x][y];
    if (dir == 1) ret = max(dp(x, y - 1, 1), dp(x + 1, y, 0)) + cost[x][y];
    if (dir == 2) ret = max(dp(x, y + 1, 2), dp(x + 1, y, 0)) + cost[x][y];
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> cost[i][j];
        }
    }
    memset(memo, -1, sizeof(memo));
    cout << dp(1, 1, 0);
}