[BOJ - Gold IV] 곡예 비행 / ⭕

곡예 비행

 

1. 제출코드 (3시간 32분 43초 / DP)

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

public class Main {
    static int N, M;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        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];
        int[][] dp = new int[N][M];
        int[][] ddp = 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[i][j] = Integer.MIN_VALUE;
                ddp[i][j] = Integer.MIN_VALUE;
            }
        }
        dp[N - 1][0] = map[N - 1][0];
        ddp[N - 1][M - 1] = map[N - 1][M - 1];

        for(int i = 0; i < M; i++) {
            for(int j = N - 1; j >= 0; j--) {
                // 아래
                if(i == 0) {
                    if(j == N - 1) continue;
                    dp[j][i] = dp[j + 1][i] + map[j][i];
                    // 왼쪽
                } else if(j == N - 1) {
                    if(i == 0) continue;
                    dp[j][i] = dp[j][i - 1] + map[j][i];
                } else {
                    dp[j][i] = Math.max(dp[j][i - 1], dp[j + 1][i]) + map[j][i];
                }
            }
        }

        for(int i = N - 1; i >= 0; i--) {
            for(int j = M - 1; j >= 0; j--) {
                if (i == N - 1) {
                    if(j == M - 1) continue;
                    ddp[i][j] = ddp[i][j + 1] + map[i][j];
                } else if (j == M - 1) {
                    if(i == N - 1) continue;
                    ddp[i][j] = ddp[i + 1][j] + map[i][j];
                } else {
                    ddp[i][j] = Math.max(ddp[i][j + 1], ddp[i + 1][j]) + map[i][j];
                }
            }
        }

        int answer = Integer.MIN_VALUE;

        for(int i = 0; i < N ; i++) {
            for(int j = 0; j < M; j++) {
                answer = Math.max(answer, dp[i][j] + ddp[i][j]);
            }
        }
        System.out.println(answer);
    }
}

 

2. 구현 로직

DP 배열에 상승할 때의 경우와 하강할 때의 경우를 나누고 각 칸마다 가질 수 있는 최대값을 저장한다. 그러고 두개의 DP 배열을 더하면 최댓값을 구할 수 있게 된다.

1. 2개의 DP배열을 생성하고 초기화
2. 상승 DP 배열은 N - 1, 0부터 시작이므로 map[N-1][0] 값을 초기화하고 하강 DP 배열은 N-1,M-1부터 시작해서 0,0까지 탐색하는 것으로 map[N-1][M-1]을 초기화
3. 상승의 경우 왼쪽이랑 밑에서 오는 경우만 고려하면 된다.
4. 하강의 경우 역으로 생각하여 오른쪽이랑 밑에서 오는 경우만 고려하면 된다.
5. 2개의 DP 배열 값을 구하고 dp[i][j] + ddp[i][j]의 최댓값을 구하면 정답

 

3. 유의할 점

• 처음에는 BFS를 이용해서 로직을 구현했지만 시간초과가 발생했다. N과 M의 범위를 체크해서 시간복잡도를 고려했어야 했는데 그러지 못했다.