[백준] 17485 진우의 달 여행 (Large) c++

개요

인터넷에 유사한 풀이가 없어 해당 문제의 솔루션을 공유합니다.

 

체크리스트

• DP 문제 유형임을 알고 접근했는가?
• DP 3차원 자료구조로 풀이를 작성했는가?

 

접근 방법

DP[i][j][k] 는 i행, j열에 왔을 때, 마지막으로 k 방향(0, 1, 2)으로 움직여 도착한 모든 경우의 수 중 최소 비용입니다.

예를 들어 DP[i][j][0] 은 DP[i-1][j+1][1] 과 DP[i-1][j+1][2] 중 더 작은 값과 현재 위치의 비용을 더한 값이 됩니다. (i-1행 j+1열에서 왼쪽으로 이동하여 i행 j열로 도착했기 때문)

솔루션을 간단하게 작성하기 위해 벡터의 크기를 +2 하여 2e9 (int 자료형에 담을 수 있는 정수 중 최댓값 근사값) 을 저장했습니다. 

 

솔루션

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
vector < vector<int> > MAP(1002, vector<int>(1002, 0));
vector < vector< vector<int> > > DP(1002, vector< vector<int> >(1002, vector<int>(3, 2e9)));

/*
[i][j] 에 오기까지 최소 비용
고려해야 할 경우의 수 지난 거리에서 왼쪽, 아래, 오른쪽 방향으로 왔을 때의 각 최소 비용
*/
int main(){
    // 입력부
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int tmp; cin >> tmp;
            MAP[i][j] = tmp;
            
            if(i==1){
                DP[i][j][0] = MAP[i][j];
                DP[i][j][1] = MAP[i][j];
                DP[i][j][2] = MAP[i][j];
            }
        }
    }

    // DP
    for(int i=2; i<=n; i++){
        for(int j=1; j<=m; j++){
            // 현재 위치에 오기위해 0, 1, 2방향으로 이동했던 경우
            DP[i][j][0] = min(DP[i-1][j+1][1], DP[i-1][j+1][2]) + MAP[i][j];
            DP[i][j][1] = min(DP[i-1][j][0], DP[i-1][j][2]) + MAP[i][j];
            DP[i][j][2] = min(DP[i-1][j-1][0], DP[i-1][j-1][1]) + MAP[i][j];
        }
    }
    
    // 마지막 ROW에서 최솟값 찾아 출력
    int answer = 2e9;
    for(int j=1; j<=m; j++){
        for(int k=0; k<3; k++){
            if(answer > DP[n][j][k]){
                answer = DP[n][j][k];
            }
        }
    }
    
    cout << answer << '\n';
    
    return 0;
}

 

문제

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