백준 21923[자바] java 곡예 비행

문제 링크: https://www.acmicpc.net/problem/21923

21923번: 곡예 비행

▶문제

동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 점수는 "상승 비행을 할 때 지나간 칸에 부여된 점수의 총합"과 "하강 비행을 할 때 지나간 칸에 부여된 점수의 총합"을 더한 값이다. 출발한 칸과 도착한 칸도 지나간 칸으로 간주한다.

<그림 1> 시작과 끝 칸 및 가능한 이동 방향

모형 비행기는 맨 왼쪽 아래 칸에서 상승 비행으로 비행을 시작해야 하고, 중간에 상승 비행에서 하강 비행으로 변경한 후, 맨 오른쪽 아래 칸에서 하강 비행으로 비행을 종료해야 한다. 상승 비행에서 하강 비행으로 변경할 때에는 다른 칸으로 이동할 수 없다. 즉, 상승 비행이 끝난 칸에서 하강 비행을 시작해야 한다.

모형 비행기는 상승 비행 중에는 앞 또는 위로만 이동할 수 있고, 하강 비행 중에는 앞 또는 아래로만 이동할 수 있다.

<그림 2> 모형 비행기의 이동 경로

위의 예시에서, 각 칸에 적힌 수는 그 칸에 부여된 점수이고, 수가 적혀 있지 않은 칸의 점수는 0이라고 가정하자. 그리고 모형 비행기가 1, 2,..., 15의 순서대로 비행을 했다고 가정하자.

<그림 3> 상승 비행의 이동 경로

<그림 4> 하강 비행의 이동 경로

이 경우, 상승 비행은 1이 적힌 칸에서 시작하고 8이 적힌 칸에서 끝난다. 하강 비행은 8이 적힌 칸에서 시작하고 15가 적힌 칸에서 끝난다. 이와 같이 비행을 하였을 때 얻는 점수는 (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8) + (8 + 9 + 10 + 11 + 12 + 13 + 14 + 15) = 128이다.

동헌이는 이 대회에서 얻을 수 있는 최대 비행 점수가 궁금하다. 동헌이를 위해 얻을 수 있는 최대 비행 점수를 구해주자.

---

▶입력

첫째 줄에 심사위원들이 나눠놓은 구역(격자)의 세로 길이 N, 가로길이M이 공백과 함께 주어진다.

두 번째 줄부터 N+1번째 줄까지, 각 칸에 해당하는 점수가 한 줄에 한 행씩 공백과 함께 주어진다.

---

▶출력

동헌이가 얻을 수 있는 최대 점수를 출력하라.

---

▶해설

DP를 두 가지로 나눠서 푸는 것이었습니다. 조건을 살펴보겠습니다.

1. 상승 구간은 오른쪽, 위로밖에 갈 수 없다. 

2. 하강 구간은 오른쪽, 아래로 밖에 갈 수 없다.

3. 왼쪽 아래에서 시작하며, 오른쪽 아래에서 끝난다. 

 

따라서 DP를 올라갈 때와 내려갈 때를 나눠서 구하고, 더하면 해결됩니다. 

 

상승일 때를 먼저 살펴보겠습니다. 

 

1. 3과 2의 경우 밑에서 올라오는 한 가지의 경우의 수입니다.

2. 마찬가지로 4,7,11 또한 왼쪽에서 오는 한 가지의 경우의 수입니다. 

3. 5~9,13은 왼쪽에서 오는 것과 아래쪽에서 오는 것을 비교해서 더 큰 것을 집어넣어 줍니다. 

 

하락일 때 살펴보겠습니다. 

 

1. 가장 위의 라인인 3,6,9,13 왼쪽에서 온 것만 넣어줍니다..

2. 4,7,5,8,11의 경우 위에서 내려온 것과 왼쪽에서 비교해서 큰 값을 넣어줍니다.

 

전부 구했다면 각각의 dp를 더해주면 완성됩니다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        max = Math.max(dpDown[i][j]+ dpUP[i][j] , max);
    }
}

전체 코드 

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


public class Main {
    static int n , m;
    static int max;
    static int [][] map;
    static int [][] dpUP, dpDown ;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");

        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        max = -100000000;
        map = new int[n][m];
        dpUP = new int[n][m];
        dpDown = new int[n][m];
        for (int i = 0; i < n; i++) {
            String[] s1 = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(s1[j]);
            }
        }

        br.close();

        dpUP[n-1][0] = map[n-1][0];
        for (int i = n-1; i >=0; i--) {
            if(i!=n-1) {
                dpUP[i][0] = dpUP[i+1][0] + map[i][0];
            }
            for (int j = 1; j < m; j++) {
                if(i!=n-1) {
                    dpUP[i][j] = Math.max(dpUP[i+1][j], dpUP[i][j-1])+ map[i][j];
                }
                else {
                    dpUP[i][j] =  dpUP[i][j-1] + map[i][j];
                }
            }
        }

        dpDown[n-1][m-1] = map[n-1][m-1];
        for (int i = n-1; i >=0; i--) {
            if(i!=n-1) {
                dpDown[i][m-1] = dpDown[i+1][m-1] + map[i][m-1];
            }
            for (int j = m-2; j >=0; j--) {
                if(i!=n-1) {
                    dpDown[i][j] = Math.max(dpDown[i+1][j], dpDown[i][j+1])+ map[i][j];
                }
                else {
                    dpDown[i][j] = dpDown[i][j+1] + map[i][j];
                }

            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                max = Math.max(dpDown[i][j]+ dpUP[i][j] , max);
            }
        }

        System.out.println(max);
    }
}