[백준(Baekjoon)][자바(java)] 2096 : 내려가기 / 동적계획법

 

www.acmicpc.net/problem/2096

2096번: 내려가기

 

문제 풀이

 

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

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int a[][] = new int[n][3], i, j;
		StringTokenizer st;
		for (i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (j = 0; j < 3; j++)
				a[i][j] = Integer.parseInt(st.nextToken());
		}
		br.close();

		int dp_max[][] = new int[n][3], dp_min[][] = new int[n][3];
		for (i = 0; i < n; i++)
			for (j = 0; j < 3; j++)
				dp_max[i][j] = dp_min[i][j] = a[i][j];
		for (i = 0; i < n - 1; i++) {
			// 최대값
			dp_max[i + 1][0] += Math.max(dp_max[i][0], dp_max[i][1]);
			dp_max[i + 1][1] += Math.max(Math.max(dp_max[i][0], dp_max[i][1]),dp_max[i][2]);
			dp_max[i + 1][2] += Math.max(dp_max[i][1], dp_max[i][2]);
			// 최소값
			dp_min[i + 1][0] += Math.min(dp_min[i][0], dp_min[i][1]);
			dp_min[i + 1][1] += Math.min(Math.min(dp_min[i][0], dp_min[i][1]),dp_min[i][2]);
			dp_min[i + 1][2] += Math.min(dp_min[i][1], dp_min[i][2]);
		}

		int max = Math.max(Math.max(dp_max[n - 1][0], dp_max[n - 1][1]), dp_max[n - 1][2]),
			min = Math.min(Math.min(dp_min[n - 1][0], dp_min[n - 1][1]), dp_min[n - 1][2]);
		System.out.println(max + " " + min);
	}
}

 

*  DP

-  dp[][] 배열을 두 개 생성 ( dp_min[][] 최솟값, dp_max[][] 최댓값 )
   dp[i][j] => i 행 j열에서 0~i번째 행까지 얻을 수 있는 값들의 합 ( 최솟값 / 최댓값 )

-  문제에 나온 설명은 윗줄 기준으로, 윗줄에서 아랫줄로 내려갈 시 바로 밑이나 그 옆으로만 갈 수 있다고 나와있다.
   아랫줄 기준으로 본다면, 바로 위나 그 옆에서만 아래줄에 도달할 수 있다는 것이다.

-  dp[i+1][j]  ☞  dp[i][j] 나 그 옆 값 중 더 큰 / 작은 수