[ 백준 / java ] 21923 곡예비행

문제 링크

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

21923번: 곡예 비행

문제 풀이

DP 문제이다. https://www.acmicpc.net/problem/1932 를 풀고 풀면 더 쉽게 풀 수 있을 것 같다.

1. DP를 통해서 올라가는 방향의 점수를 2차원 배열에 저장한다.

2. DP를 통해서 내려가는 방향의 점수를 2차원 배열에 저장한다.

3. 두 배열을 각 지점마다 더하고 MAX값을 비교해 출력한다.

 

풀고나면 생각보다 간단한 문제인 것 같다.

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class P21923 {
	static int N , M;
	static int max;
	static int [][] score;
	static int [][] upMove, dwMove ;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine(), " ") ;
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		max = -999999999;
		score = new int[N][M];
		upMove = new int[N][M];
		dwMove = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ") ;
			for (int j = 0; j < M; j++) {
				score[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		br.close();
		
		//올라가는 방향
		upMove[N-1][0] = score[N-1][0];
		for (int i = N-1; i >= 0; i--) {
			
			if(i!=N-1) upMove[i][0] = upMove[i+1][0] + score[i][0];
			for (int j = 1; j < M; j++) {
				if(i!=N-1) upMove[i][j] = Math.max(upMove[i+1][j], upMove[i][j-1])+ score[i][j];
				else upMove[i][j] =  upMove[i][j-1] + score[i][j];
			}
		}
		
		//내려가는 방향
		dwMove[N-1][M-1] = score[N-1][M-1];
		for (int i = N-1; i >= 0; i--) {
			if(i!=N-1) dwMove[i][M-1] = dwMove[i+1][M-1] + score[i][M-1];
			for (int j = M-2; j >=0; j--) {
				if(i!=N-1) dwMove[i][j] = Math.max(dwMove[i+1][j], dwMove[i][j+1])+ score[i][j];
				else dwMove[i][j] = dwMove[i][j+1] + score[i][j];
						
			}
		}
		
		//올라가는 점수 + 내려가는점수
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				max = Math.max(dwMove[i][j]+ upMove[i][j] , max);
			}
		}
		
		System.out.println(max);
	}
	
	
	
	

}