[백준] 2096번 내려가기 (자바 풀이)

문제

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

2096번: 내려가기

 

풀이

이 문제는 간단한 DP 문제였다. maxDp와 minDP를 따로 나누어서 해결하면 간단하다.

 

우선, maxDp의 경우는 아래와 같은 점화식을 세우면 된다.

maxDp[i][j] = i번째 줄에서 j번째 숫자를 선택할 때 최댓값 ( 0 <= j < 3 )

maxDp[i][0] = Math.max(maxDp[i-1][0], maxDp[i-1][1]) + arr[i][0];
maxDp[i][1] = Math.max(Math.max(maxDp[i-1][0], maxDp[i-1][1]), maxDp[i-1][2]) + arr[i][1];
maxDp[i][2] = Math.max(maxDp[i-1][1], maxDp[i-1][2])+arr[i][2];

0번째 숫자를 고르는 것은 이전에 0번 혹은 1번에서 내려왔을테니 이들 중 최댓값을 고르고

1번째 숫자를 고르는 것은 이전에 0번,1번,2번 에서 내려왔을 테니 이들 중 최댓값을 고르고

2번째 숫자를 고르는 것은 이전에 1번 혹은 2번에서 내려왔을테니 이들 중 최댓값을 고르면 된다.

 

minDp의 경우는 위와 반대로 점화식을 세우면 된다.

minDp[i][j] = i번째 줄에서 j번째 숫자를 선택할 때 최솟값 ( 0 <= j < 3 )

minDp[i][0] = Math.min(minDp[i-1][0], minDp[i-1][1]) + arr[i][0];
minDp[i][1] = Math.min(Math.min(minDp[i-1][0], minDp[i-1][1]), minDp[i-1][2]) + arr[i][1];
minDp[i][2] = Math.min(minDp[i-1][1], minDp[i-1][2])+arr[i][2];

 

코드

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

public class Baekjoon_2096 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int arr[][] = new int[N][3];
		int maxDp[][] = new int[N][3];
		int minDp[][] = new int[N][3];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
			arr[i][2] = Integer.parseInt(st.nextToken());
		}
		
		maxDp[0][0] = minDp[0][0] = arr[0][0]; 
		maxDp[0][1] = minDp[0][1] = arr[0][1];
		maxDp[0][2] = minDp[0][2] = arr[0][2];
		
		for(int i=1; i<N; i++) {
			maxDp[i][0] = Math.max(maxDp[i-1][0], maxDp[i-1][1]) + arr[i][0];
			maxDp[i][1] = Math.max(Math.max(maxDp[i-1][0], maxDp[i-1][1]), maxDp[i-1][2]) + arr[i][1];
			maxDp[i][2] = Math.max(maxDp[i-1][1], maxDp[i-1][2])+arr[i][2];
			
			minDp[i][0] = Math.min(minDp[i-1][0], minDp[i-1][1]) + arr[i][0];
			minDp[i][1] = Math.min(Math.min(minDp[i-1][0], minDp[i-1][1]), minDp[i-1][2]) + arr[i][1];
			minDp[i][2] = Math.min(minDp[i-1][1], minDp[i-1][2])+arr[i][2];
			
		}
		
		int max = Math.max(maxDp[N-1][0], Math.max(maxDp[N-1][1], maxDp[N-1][2]));
		int min = Math.min(minDp[N-1][0], Math.min(minDp[N-1][1], minDp[N-1][2]));
		
		System.out.println(max +" " + min);
	}
}