[백준 Gold 4] 21923 곡예 비행 - Java

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

21923번: 곡예 비행

 

접근 과정 : 

• 상승 비행과 하강 비행을 따로 관리 (상승 구간과 하강 구간이 중복되는 칸이 1~N개 있다!!!)
• 상승 비행이 끝나는 칸 == 하강 비행이 시작하는 칸
• 비행 점수 = (r,c)까지 상승한 경우 + (r,c)부터 하강하는 경우
• DP로 하강 비행을 탐색하고 하강 비행 탐색 로직 내부에서 상승 비행 탐색을 수행
• 하강비행 = (r,c)까지 상승비행 + (r,c)부터 하강비행  OR (r-1,c)부터 하강비행 OR (r,c-1)부터 하강비행

 

소스 코드 및 결과 : 

package BOJ;

/* 
    곡예 비행

    1. 해당 좌표까지 상승으로 얻을 수 있는 최대 값 
    2.  + 해당 좌표부터 하강으로 얻을 수 있는 최대 값

*/

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

public class BOJ21923 {

    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());

        board = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        upDP = new int[N][M];
        downDP = new int[N][M];

        upVisit = new boolean[N][M];
        downVisit = new boolean[N][M];

        int max = findDown(N-1, M-1);
       
        System.out.println(max);

    }

    static int N, M;
    static int[][] board;
    static int INF = -40000000;
    static int[][] upDP;
    static int[][] downDP;
    static boolean[][] upVisit; 
    static boolean[][] downVisit;

    static int findUP(int r, int c) {

        if (upVisit[r][c]) {
            return upDP[r][c];
        }
        upVisit[r][c] = true;

        if (r == N - 1 && c == 0) {
            return upDP[r][c] = board[N - 1][0];
        }

        if (r == N - 1) {
            return upDP[r][c] = findUP(r, c - 1) + board[r][c];
        }

        if (c == 0) {
            return upDP[r][c] = findUP(r + 1, c) + board[r][c];
        }

        return upDP[r][c] = Math.max(findUP(r + 1, c), findUP(r, c - 1)) + board[r][c];
    }

    static int findDown(int r, int c) {

        if (downVisit[r][c]) {
            return downDP[r][c];
        }

        downVisit[r][c] = true;

        if (r == 0 && c == 0) {
            return downDP[r][c] = findUP(0,0)+board[0][0];
        }

        if (r == 0) {
            return downDP[r][c] = Math.max(findUP(r, c), findDown(r, c - 1)) + board[r][c];
        }

        if (c == 0) {
            return downDP[r][c] = Math.max(findUP(r, c), findDown(r - 1, c)) + board[r][c];
        }
        

        return downDP[r][c] = Math.max(findUP(r, c), Math.max(findDown(r - 1, c), findDown(r, c - 1))) + board[r][c];

    }

}

 

 

P.S

범위에 대한 부분을 좀 더 깔끔하게 정리할 수 있지 않을까....