[백준 2096번] 내려가기

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

2096번: 내려가기

이 문제는 dp를 이용한 문제입니다.

---

풀이법

이 문제는 전단계의 값들과 자신의 값을 더한 것중 최댓값과 최솟값을 찾으며 비교하는 문제입니다. 푸는 방법은 다음과 같습니다.

1.1번쨰 자리에서 시작할 경우 전단계의 1번째자리와 2번째자리의 값중 최댓값과 최솟값을 찾는다
2.2번째 자리에서 시작할 경우 전단계의 1번째 자리와 2번째 자리, 그리고 3번째 자리중 최댓값 최솟값을 찾는다.
3. 3번째 자리에서 시작할 경우 전 단계의 2번째 자리와 3번째 자리중 최댓값 최솟값을 찾는다.

이를통해 전체 더한 값을 구한뒤 최솟값또는 최댓값을 더하면 된다.

코드

import java.util.*;

public class Main {
	public static void main(String arg[]) {
		Scanner sc=new Scanner(System.in);
		int n= sc.nextInt();
		int [][]plates=new int[n][3];
		int max=0;
		int min=999999999;
		int [][]dp=new int[n][3];
		for(int i =0;i<n;i++) {
			for(int j = 0; j<3;j++) {
				plates[i][j]=sc.nextInt();
			}
		}
		
		for(int i=0;i<3;i++)
			dp[0][i]=plates[0][i];
		
		for(int i=1;i<n;i++) {
			dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1])+plates[i][0];
			dp[i][1]=Math.max(dp[i-1][0],Math.max(dp[i-1][1], dp[i-1][2]))+plates[i][1];
			dp[i][2]=Math.max(dp[i-1][1], dp[i-1][2])+plates[i][2];
		}
		max=Math.max(dp[n-1][0],Math.max(dp[n-1][1],dp[n-1][2]));
		for(int i=1;i<n;i++) {
			dp[i][0]=Math.min(dp[i-1][0], dp[i-1][1])+plates[i][0];
			dp[i][1]=Math.min(dp[i-1][0],Math.min(dp[i-1][1], dp[i-1][2]))+plates[i][1];
			dp[i][2]=Math.min(dp[i-1][1], dp[i-1][2])+plates[i][2];
		}
		min=Math.min(dp[n-1][0],Math.min(dp[n-1][1],dp[n-1][2]));
		
		System.out.println(max+" "+min);
	}

	
}