백준 17485 진우의 달 여행 (Large) 혼내주기

 

완전탐색 + dp 문제.
시작점에서는 모든 방향으로 움직일 수 있기 때문에 이중 for문으로 출발점을 일일이 찍어주면 방향 때문에 dp 배열 크기를 4로 하지 않아도 된다.
이 문제를 풀면 17484 진우의 달 여행 (Small) 문제를 날로 먹을 수 있다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int dy[3] = {-1, 0, 1};

int map[1000][1000], cache[1000][1000][3];
int n, m;

int d(int x, int y, int dir){
    if(x == n) return 0;

    int& ret = cache[x][y][dir];
    if(ret != -1) return ret;

    ret = 1e9;
    for(int i = 0 ; i < 3; ++i){
        if(dir == i || y + dy[i] < 0 || y + dy[i] >= m) continue;
        ret = min(ret, d(x+1, y + dy[i], i) + map[x][y]);
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> map[i][j];
        }
    }
    memset(cache, -1, sizeof(cache));
    int ans = 1e9;
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < 3; ++j){
            ans = min(ans, d(0, i, j));
        }
    }
    cout << ans << endl;
}