[백준] 17484번 진우의 달 여행 (Small)

문제 출처: https://www.acmicpc.net/problem/17484

17484번: 진우의 달 여행 (Small)

moon(n,m,내가 다음에 움직일 방향)으로 재귀함수를 작성한다.

위 함수는 moon(n-1,m + 내가 이전에 움직인 방향, 내가 이전에 움직인 방향)을 호출한다.

이때 2번의 같은 방향으로 움직이는 것은 불가능하기 때문에 내가 다음에 움직일 방향 != 내가 이전에 움직인 방향이다.

Small에서는 메모이제이션을 사용하지 않아도 통과한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>

using namespace std;

int N, M;
int arr[1001][1001];
int dp[1001][1001][3];
int movePos[3] = { -1,0,1 };
const int INF = 123456789;

int moon(int n, int m, int dir) {
    if (n == -1)return 0;
    if (dp[n][m][dir] != INF)return dp[n][m][dir];
    
    int minV = INF;
    for (int i = 0; i < 3; i++) {
        if (i == dir)continue;
        if (m + movePos[i] < 0 || m + movePos[i] >= M)continue;

        minV = min(minV, moon(n - 1, m + movePos[i], i) + arr[n][m]);
    }

    dp[n][m][dir] = minV;
    
    return minV;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < 3; k++) {
                dp[i][j][k] = INF;
            }
        }
    }

  
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }

    int minV = INF;
    
    for (int j = 0; j < M; j++) {
        for (int i = 0; i < 3; i++) {
            minV = min(minV,moon(N-1, j, i));
        }
    }

    cout << minV;
    
    

}