[백준/17485] 진우의 달 여행 (Large) - JAVA

이지환·2025년 5월 8일

백준 알고리즘

알고리즘(백준) 💻

목록 보기

62/80

📌 문제

알고리즘 분류 : DP
난이도 : 골드5
출처 : 백준 - 진우의 달 여행 (Large)

🦧 문제 풀이 접근

DP로 문제를 해결 할 수 있다.
이때 DP배열을 3차원 배열로 만들어서 3방향에서 온 값을 모두 저장한다.

예시 이미지에서 1,2의 값은 8일다.
그럴경우 DP[1][2][0]은 왼쪽 대각선 칸에서의 최소값을 더해 16
DP[1][2][1]은 바로 위칸에서의 최소값을 더해 13
DP[1][2][2]은 오른쪽 대각선 칸에서의 최소값을 더해 9가 된다.

이때 가장 왼쪽, 오른쪽 칸에 경우 MaxValue로 예외처리를 한다.

💻 code

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int map[][] = new int[N][M];
        int DP[][][] = new int[N][M][3];
        // \->0, |->1, /->2
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }

        }
        for(int j=0;j<M;j++) {
            DP[0][j][0] = map[0][j];
            DP[0][j][1] = map[0][j];
            DP[0][j][2] = map[0][j];
        }
        for(int i=1;i<N;i++) {
            DP[i][0][0] = Integer.MAX_VALUE;
            DP[i][0][1] = Integer.min(DP[i-1][0][0],DP[i-1][0][2])+map[i][0];
            DP[i][0][2] = Integer.min(DP[i-1][1][0],DP[i-1][1][1])+map[i][0];
            for(int j=1;j<M-1;j++) {
                DP[i][j][0] = Integer.min(DP[i-1][j-1][1],DP[i-1][j-1][2])+map[i][j];
                DP[i][j][1] = Integer.min(DP[i-1][j][0],DP[i-1][j][2])+map[i][j];
                DP[i][j][2] = Integer.min(DP[i-1][j+1][0],DP[i-1][j+1][1])+map[i][j];
            }
            DP[i][M-1][0] = Integer.min(DP[i-1][M-2][1],DP[i-1][M-2][2])+map[i][M-1];
            DP[i][M-1][1] = Integer.min(DP[i-1][M-1][0],DP[i-1][M-1][2])+map[i][M-1];
            DP[i][M-1][2] = Integer.MAX_VALUE;
        }
        int minNum = Integer.MAX_VALUE;
        for(int i=0;i<M;i++) {
            for(int j=0;j<3;j++) {
                if(minNum>DP[N-1][i][j])
                    minNum = DP[N-1][i][j];
            }
        }
        System.out.println(minNum);
    }
}