(C++) - 백준(BOJ) 17485~6번 : 진우의 달 여행 (Small, Large)

https://www.acmicpc.net/problem/17484

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

https://www.acmicpc.net/problem/17485

17485번: 진우의 달 여행 (Large)

 

dp 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. n, m, matrix배열, d배열, ans선언 후 필요 변수를 입력받습니다.

 2. 최솟값을 구하기 위해 d배열은 INF로 초기화해줍니다.

 

📔 풀이과정

 dp함수를 1열 ~ m열까지 수행한 최솟값을 ans에 저장합니다.

 dp함수 수행

  1. 기저 : 유효 열(1 <= c <= m)이 아니라면 INF를 반환합니다. 도착했을때(r == n) 그 장소의 연료를 반환합니다.

  2. 3방향에 대해 호출 : d가 0이라면 초기이므로 어떤 방향이든 갈 수 있습니다. d가 1이면 좌하방향으로 이동입니다. 연속으로 1방향으로 갈 수 없으니 2, 3방향으로 dp함수를 호출합니다. 이런식으로 현재 지나온 방향 dir에 대해 i가 같은 방향이 아니면 갈 수 있으므로 그 곳으로 방향을 전환해 dp함수를 호출하면 됩니다.

  

 

📔 정답출력

ans를 출력합니다.

---

📕 Code

Top Down

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n, m, ans = INF;
int matrix[1001][1001], d[1001][1001][4];
int dc[] = {0, -1, 0, 1};
int dp(int r, int c, int dir){
    if(1 > c || c > m) return INF;
    if(r == n) return matrix[r][c];
    int &ret = d[r][c][dir];
    if(ret != INF) return ret;

    for(int i = 1; i <= 3; i++){
        if(i == dir) continue;
        ret = min(ret, matrix[r][c] + dp(r + 1, c + dc[i], i));
    }
    return ret;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> matrix[i][j];

    memset(d, INF, sizeof(d));

    for(int i = 1; i <= m; i++) ans = min(ans, dp(0,i,0));
    cout << ans;
}