[BOJ] 백준 2169 - 로봇 조종하기

문제 링크

www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

 

풀이

일반적인 DP이지만 방향을 잘 잡아주어야 합니다.

저 같은 경우 어느 방향에서 왔는지에 대한 정보를 함께 넘겨주어, 그 방향으로는 다시 전개를 안 하게끔 구현했습니다. (line 20)

 

 

정답 코드

#include <bits/stdc++.h>
 
#define INF 0x3f3f3f3f
using namespace std;
 
int n, m, p[1111][1111];
int dx[] = {0, 1, 0}, dy[] = {1, 0, -1};
int d[1111][1111][3];
 
bool isValid(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}
 
int go(int x, int y, int prevDir) {
    if (x == n - 1 && y == m - 1) return p[x][y];
    int &ret = d[x][y][prevDir];
    if (ret != -1) return ret;
    ret = -INF;
    for (int k = 0; k < 3; k++) {
        if ((prevDir + 2) % 4 == k) continue;
        int nx = x + dx[k], ny = y + dy[k];
        if (!isValid(nx, ny)) continue;
 
        ret = max(ret, p[x][y] + go(nx, ny, k));
    }
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> p[i][j];
        }
    }
    memset(d, -1, sizeof(d));
    cout << go(0, 0, 1);
}