[99클럽 코테 스터디 14일차 TIL] 진우의 달 여행 (Small)

 

14일차 문제

링크 : https://www.acmicpc.net/problem/17484
 
 
문제 풀이
 
처음에 어떻게 접근할지 몰라 구글링 후 dp 3차원 배열을 만들어서 풀이하였다.
총 3가지 방향으로 접근이 가능하므로, dp[N][M][3] 배열을 생성한다.

   > 0 : 왼쪽 하단 방향
   > 1 : 직진 하단 방향
   > 2 : 우측 하단 방향
 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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[][] arr = new int[N][M];
        int[][][] dp = new int[N][M][3]; // 3 : 이전 방향을 저장하기 위해

        /**
         * 6 4
         * 5 8 5 1
         * 3 5 8 4
         * 9 77 65 5
         * 2 1 5 2
         * 5 98 1 5
         * 4 95 67 58
         */

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                Arrays.fill(dp[i][j], Integer.MAX_VALUE);
            }
        }

        // dp 시작 배열 초기화
        for(int i=0; i<M; i++) {
            dp[0][i][0] = arr[0][i];
            dp[0][i][1] = arr[0][i];
            dp[0][i][2] = arr[0][i];
        }

        // k : 0 -> 왼쪽 하단으로
        // k : 1 -> 중앙으로
        // k : 2 -> 우측 하단으로

        for(int i=1; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(j==0) {
                    // 직진으로 내려오거나 왼쪽 하단으로만 내려올 수 있음

                    // 1. 중앙
                    dp[i][j][1] = dp[i-1][j][0] + arr[i][j];

                    // 2. 왼쪽 하단 : 직전 방향은 1,2번이 가능
                    dp[i][j][0] = Math.min(dp[i-1][j+1][1], dp[i-1][j+1][2]) + arr[i][j];
                }

                if(j>=1 && j<M-1) {
                    dp[i][j][0] = Math.min(dp[i-1][j+1][1], dp[i-1][j+1][2]) + arr[i][j];
                    dp[i][j][1] = Math.min(dp[i-1][j][0], dp[i-1][j][2]) + arr[i][j];
                    dp[i][j][2] = Math.min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + arr[i][j];
                }

                if(j==M-1) {
                    // 직진으로 내려오거나 우측 하단으로만 내려올 수 있음
                    dp[i][j][1] = dp[i-1][j][2] + arr[i][j];
                    dp[i][j][2] = Math.min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + arr[i][j];
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for(int i=0; i<M; i++) {
            for(int j=0; j<3; j++) {
                min = Math.min(min, dp[N-1][i][j]);
            }
        }
        System.out.println(min);
    }
}