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

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

---

 

문제)

우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.

 

 

진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.

1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.

 

 

2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.

진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.

최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산해 주자.

 

 

입력 :

첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다.

다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.

 

 

 

출력 :

달 여행에 필요한 최소 연료의 값을 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
int n, m;
vector<vector<int>> vec;
 
// 현재 위치 [행]
// 현재 열 위치 [열]
// 이전 방향
// 현재까지의 연료 필요량
//을 기반으로한 4차원 dp를 활용한다.
int dp[7][7][4][1000];
 
int dx[] = { -1, 0, 1 };
 
int recur(int cur, int idx, int prev, int total)
{
    int ret = INT_MAX;
 
    if (cur == n)
    {
        return total;
    }
 
    if (dp[cur][idx][prev][total] != -1)
    {
        return dp[cur][idx][prev][total];
    }
 
 
    for (int i = 0; i < 3; i++)
    {
 
        int ny = idx + dx[i];
        if (ny >= 0 && ny < m && i != prev)
        {
            ret = min(ret, recur(cur + 1, ny, i, total + vec[cur][idx]));
        }
    }
 
    dp[cur][idx][prev][total] = ret;
 
    return dp[cur][idx][prev][total];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        int t;
        vector<int> temp;
        for (int j = 0; j < m; j++)
        {
            cin >> t;
            temp.push_back(t);
        }
        vec.push_back(temp);
    }
 
    fill(&dp[0][0][0][0], &dp[0][0][0][0] + 7 * 7 * 4 * 1000, -1);
 
    // 처음 지구에서 출발할 때
    // m가지 출발이 가능하다.
    int result = INT_MAX;
    for (int i = 0; i < m; i++)
    {
        result = min(result, recur(0, i, 3, 0));
    }
 
    cout << result;
 
    return 0;
}

 

---

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

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