[백준/Baekjoon] 진우의 달 여행 17484 C++ :: Brute force & Dynamic programming

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

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

---

1. Logic

브루트 포스로 풀 수 있지만 각 칸에서의 최솟값은 변하지 않기 때문에 그 값을 저장해 놓고 DP로 풀이할 수 있다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n, m;

int space[10][10];
int dp[10][10][4];


//0:왼 1:dir 2:오
int solve(int y, int x, int prev) {
    if(y == n) return 0;
    int &ret = dp[y][x][prev];
    
    if(ret != -1) return ret;
    
    ret = 0x3f3f3f3f;
    
    if(x-1 >= 0 && prev != 0) {
        ret = min(ret, solve(y+1, x-1, 0) + space[y][x]);
    }
    
    if(x+1 < m && prev != 2) {
        ret = min(ret, solve(y+1, x+1, 2) + space[y][x]);
    }
    
    if(prev != 1) {
        ret = min(ret, solve(y+1, x, 1)+space[y][x]);
    }
    
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> space[i][j];
        }
    }
    
    int ans = 0x3f3f3f3f;
    
    for(int i = 0; i < m; i++) {
        ans = min(ans, solve(0, i, 3));
    }
    
    cout << ans;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90