자바 | 백준 | 2096 | 내려가기

Solution. DP 이용

1열, 2열, 3열 각각 최소값, 최대값 구한다.

// 2096, 내려가기
package BOJ;

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

public class BOJ_2096 {

	static int N;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		int[][] map = new int[N + 1][3];
		int[][] dp_max = new int[N + 1][3];
		int[][] dp_min = new int[N + 1][3];

		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			// map에 입력 받음
			map[i][0] = Integer.parseInt(st.nextToken());
			map[i][1] = Integer.parseInt(st.nextToken());
			map[i][2] = Integer.parseInt(st.nextToken());

			// dp_max 현재높이의 최댓값을 갱신
			dp_max[i][0] = Math.max(dp_max[i - 1][0], dp_max[i - 1][1]) + map[i][0];
			dp_max[i][1] = Math.max(dp_max[i - 1][0], Math.max(dp_max[i - 1][1], dp_max[i - 1][2])) + map[i][1];
			dp_max[i][2] = Math.max(dp_max[i - 1][1], dp_max[i - 1][2]) + map[i][2];

			// dp_min 현재높이의 최솟값을 갱신
			dp_min[i][0] = Math.min(dp_min[i - 1][0], dp_min[i - 1][1]) + map[i][0];
			dp_min[i][1] = Math.min(dp_min[i - 1][0], Math.min(dp_min[i - 1][1], dp_min[i - 1][2])) + map[i][1];
			dp_min[i][2] = Math.min(dp_min[i - 1][1], dp_min[i - 1][2]) + map[i][2];
			
		} 
		
		System.out.println(Math.max(dp_max[N][0], Math.max(dp_max[N][1], dp_max[N][2]))+" "+Math.min(dp_min[N][0], Math.min(dp_min[N][1], dp_min[N][2])));

	}
}

 

www.acmicpc.net/problem/2096

2096번: 내려가기