[백준 2096] 내려가기- Java

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

2096번: 내려가기

풀이

다이나믹 프로그래밍으로 구현하였다.

map[r][c] : (r, c)의 값

max[r][c] : (r, c)를 선택했을 때 max값

min[r][c] : (r, c)를 선택했을 때 min값

 

ex) max[r][1] = max(max[r-1][0], max[r-1][1], max[r-2][1]) + map[r][1]

 

 

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

public class 내려가기 {
	static int N;
	static int[][] map;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][3];

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

		int[][] max = new int[N][3];
		int[][] min = new int[N][3];
		
		for(int i = 0; i < 3; i++) {
			max[0][i] = map[0][i];
			min[0][i] = map[0][i];
		}
		for(int r = 1; r < N; r++) {
			max[r][0] = Math.max(max[r-1][0], max[r-1][1]) + map[r][0];
			max[r][1] = Math.max(Math.max(max[r-1][0], max[r-1][1]), max[r-1][2]) + map[r][1];
			max[r][2] = Math.max(max[r-1][1], max[r-1][2]) + map[r][2];
			min[r][0] = Math.min(min[r-1][0], min[r-1][1]) + map[r][0];
			min[r][1] = Math.min(Math.min(min[r-1][0], min[r-1][1]), min[r-1][2]) + map[r][1];
			min[r][2] = Math.min(min[r-1][1], min[r-1][2]) + map[r][2];
		}
		
		int resultMin = Math.min(Math.min(min[N-1][0], min[N-1][1]), min[N-1][2]);
		int resultMax = Math.max(Math.max(max[N-1][0], max[N-1][1]), max[N-1][2]);
		System.out.println(resultMax + " " + resultMin);
	}

}