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

🔺 문제

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

 

 

🔺 코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int n, m;
    static int map[][];
    static int dp[][][];
    
    static int max = 999999;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        map = new int[n][m];
        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());
            }
        }
        
        // dp 배열 초기화
        dp = new int[n][m][3];
        for (int i = 0; i < m; i++) {
            dp[0][i][0] = map[0][i]; // 왼쪽 대각선
            dp[0][i][1] = map[0][i]; // 가운데
            dp[0][i][2] = map[0][i]; // 오른쪽 대각선
        }
 
        // dp 배열 채우기
        for (int i = 1; i < n; i++) {
            // max 값으로 초기화
            dp[i][0][0] = max;
            dp[i][m - 1][2] = max;
          
            for (int j = 0; j < m; j++) {
                // 오른쪽에서 못 오는 경우
                if (!(j - 1 < 0 || j - 1 >= m) && (j + 1 < 0 || j + 1 >= m)) {
                    dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + map[i][j];
                    dp[i][j][1] = Math.min(dp[i - 1][j][0] , dp[i - 1][j][2]) + map[i][j];
                }
                // 양쪽에서 올 수 있는 경우
                else if (!(j - 1 < 0 || j - 1 >= m) && !(j + 1 < 0 || j + 1 >= m)) {
                    dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + map[i][j];
                    dp[i][j][1] = Math.min(dp[i - 1][j][0] , dp[i - 1][j][2]) + map[i][j];
                    dp[i][j][2] = Math.min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + map[i][j];
                }
                // 왼쪽에서 못오는 경우
                else if ((j - 1 < 0 || j - 1 >= m) && !(j + 1 < 0 || j + 1 >= m)) {
                    dp[i][j][1] = Math.min(dp[i - 1][j][0] , dp[i - 1][j][2]) + map[i][j];
                    dp[i][j][2] = Math.min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + map[i][j];
                }
            }
        }
        
        // 마지막 행에서 최소값 찾기
        int min = max;
        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);
    }
}

✅ 해결 아이디어
✔ DP
- DP 배열을 최솟값으로 채우기

 

 

---

🔺 다른 풀이들

- DFS 풀이

[BOJ/Python, Java] 백준 17484번 - 진우의 달 여행 (Small)

 

[알고리즘] Java / 백준 / 진우의 달 여행 (Large) / 17485

---

💬 느낀 점

DP 문제인 거 캐치하고... 좀 고민하다가...

내 풀이로 안 풀려서 다른 분 풀이 보고 두통 해결....

 

복습허자,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[백준] S3 17484번 진우의 달 여행 (Small) (JAVA)