알고리즘

[백준 17485] 진우의 달 여행 (Large) - 자바(java)

김RPG 2025. 4. 19. 20:56
반응형

문제

 

 

이 문제는 진우의 달 여행(small)에서 똑같은 조건이지만 N과 M이 6이 최대였던 전과 다르게 이번에는 1000이 최대이다.

 

small에서는 브루트 포스로 모든 경우를 다 구해 구할 수 있지만, Large 같은 경우에는 브루트 포스로 풀 경우 O(3^N*M) 의 시간 복잡도가 나오기 때문에 제시간내에 풀 수가 없다

 

풀이 

그렇다면 어떻게 풀어야 할까??

 

현재 자신의 위치에서 그 위에 어떤 값이 선택되었는지 중요하지 않고, 그냥 최솟값만 구하면 되는 것이다. 

그렇다면 DP로 접근이 가능하다.

 

1. 무조건 아래 방향으로 -1 0 1 이 방향으로 움직일 수 밖에 없다.

일단 이것만으로 생각해보자면

dp[i][j] = 위에서 나온 값중 최솟 값 + 지금 현재 값

이런식으로 생각할 수 있겠다.

그리구 0과 M-1 에서는 두가지 경우의 수에서만 구할 수 있도록 하기!! 

일단 여기까지 체크!!

 

2. 두번째까 좀 까다로운데 전에 움직인 방향으로 움직일 수 없다. 그러니까 두번 연속으로 같은 방향으로 움직일 수 없다

그렇다면 dp가 이중 배열로 해결하기 힘들 것 같다. 

우리는 3가지의 방향이 있으므로 dp에 [3] 배열을 추가해서

왼쪽아래로 온 경우 / 바로 아래로 온 경우 / 오른쪽 아래로 온 경우 이렇게 3가지의 경우의 수를 추가해야 할 것 같다.

 

그러면 점화식을 써보면 

N 을 도는 것이 i / M을 도는 것이 j / 현재 값이 arr[][] 배열이라 했을 경우 

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-1][0], dp[i-1][j-1][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];

라고 점화식을 세울 수 있을 것 같다.

 

물론 0 과 M-1 일 경우 예외처리를 해줘야 하는데 

// 0일 경우
dp[i][j][0] = 100_000_001;
////////////////////////////////////////////
// M-1
dp[i][j][2] = 100_000_001;

최대일 경우 N이 1000 이고 M 이 1000이고 모든 수가 100이 었을 경우를 계산해보면

1000 * 1000 * 100 = 100,000,000 을 안 넘으므로

100,000,001로 처리해 줄 경우 이 DP를 그 밑에서 고르지 않으므로 이런식으로 예외 처리 해줘도 될 것 같다!!

 

정답 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        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];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int a = Integer.parseInt(st.nextToken());
            arr[0][i] = a;
            dp[0][i][0] = a;
            dp[0][i][1] = a;
            dp[0][i][2] = a;
        }
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (j == 0) {
                    dp[i][j][0] = 100_000_001;
                    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];
                } else if (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] =  100_000_001;
                }else{
                    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];

                }
            }
        }
        int min = 100_000_001;
        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);
    }


}

 

 

반응형