[BOJ21923] 곡예 비행 (동적 프로그래밍)

 

 

---

문제링크

https://www.acmicpc.net/problem/21923

21923번: 곡예 비행

---

문제풀이

처음 격자형 그래프에 대해 BFS로 풀이하려 함 
그런데 상승에서 하강으로 바뀌는 시점에 처리가 모호했고, 제한된 시간 40분을 초과하여 
풀이 방법을 확인함

- 동적 프로그래밍 풀이

- 상승과 하강일때 dp 테이블을 각각 구한 후 반복문 돌며 합했을 때 최대치를 구하면 됨

- 시간 복잡도 : N, M이 각 1000이라 해도 대략 O( 3 * 10^6 ) 보다 적게 연산 된다.

 

예시

예제 입력 1 (정답은 23)

 

① 상승 dp 테이블 (long[][] up) 초기화

- 맨 좌측 아래 (N, 1) 에서 출발

- 시작 지점의 행과 열의 경우 자기 자신과 이전 행 또는 열 값을 더하여 초기화 수행

② 상승 dp 테이블 남은 영역 갱신 

마찬가지로 상승이기 때문에 주어진 방향 정보에 맞춰 현재 위치의 값과 이전 위치 정보 값 중 최대값을 더해 갱신

점화식*
dp[row][col] = data[row][col] + Math.max(dp[row][col - 1], dp[row + 1][col]);

2행 2열 예로 들면
dp[2][2] = data[2][2] + Math.max(dp[2][1], dp[3][1]) = -3 + 4 = 1

 

③ 하강 dp 테이블(long[][] down) 초기화 

- 하강의 경우 위치가 (N, M)으로 지정되어 있음 

- 하강 포인트와 동일한 행, 열에 대해 초기화 수행

(끝)을 기준으로 이전 정보 참고하여 방향이 헷갈릴 수 있으니 주의
3행 3열의 경우  1 + (-3) = -2
2행 4열의 경우  5 + (-3) = 2 

3행 1열의 경우 -2인데 이 뜻은
3행 1열에서 하강을 시작했을 때 얻을 수 있는 값이 -2라는 뜻

마찬가지로 1행 4열에서 하강을 시작했을 때 얻을 수 있는 값이 3이라는 뜻

 

④ 하강 dp 테이블 남은 영역 갱신 

- 2행 3열을 시작으로 데이터가 갱신된다

*점화식
dp[row][col] = field[row][col] + Math.max(dp[row + 1][col], dp[row][col + 1])

2행 3열 예로 들면 
dp[2][3] = field[2][3] + Math.max(dp[3][2], dp[2][4]) = 9 + 2 = 11

 

⑤ 2중 반복문을 돌면 상승과 하강 dp 테이블 값을 합쳤을 때 최대값을 구한다

---

제출코드

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

public class Main {
    static void pro() 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[][] fields = new int[N + 1][M + 1];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= M; j++) {
                fields[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 상승
        long[][] up = new long[N + 1][M + 1];
        up[N][1] = fields[N][1];
        for(int row = N - 1; row >= 1; row--) {
            up[row][1] = fields[row][1] + up[row + 1][1];
        }

        for(int col = 2; col <= M; col++) {
            up[N][col] = fields[N][col] + up[N][col - 1];
        }

        for(int row = N - 1; row >= 1; row--) {
            for(int col = 2; col <= M; col++) {
                up[row][col] = fields[row][col] + Math.max(up[row][col - 1], up[row + 1][col]);
            }
        }

        // 하강
        long[][] down = new long[N + 1][M + 1];
        down[N][M] = fields[N][M];
        for(int row = N - 1; row >= 1; row--) {
            down[row][M] = fields[row][M] + down[row + 1][M];
        }

        for(int col = M - 1; col >= 1; col--) {
            down[N][col] = fields[N][col] + down[N][col + 1];
        }

        for(int row = N - 1; row >= 1; row--) {
            for(int col = M - 1; col >= 1; col--) {
                down[row][col] = fields[row][col] + Math.max(down[row][col + 1], down[row + 1][col]);
            }
        }

        
        // 결과값 
        long result = Long.MIN_VALUE;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                result = Math.max(result, up[i][j] + down[i][j]);
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(result + "");
        bw.close();
        bw.close();
    }

    public static void main(String[] args) throws Exception {
        pro();
    }
    
}