백준 2096 - 내려가기

Java

2096 번 - 내려가기

문제

접근 방법

RGB거리를 풀었다면 비슷한 접근법으로 해결 가능한 문제이다.

dp를 이용하여 2번째 행부터 최대 점수와 최소 점수를 갱신한다.

문제에서는 내려가는 조건이 현재 위치에서 x 값이 [-1, 0, +1]일 때 가능하다.
따라서 역으로 현재 위치에서 지난 행까지의 최대 값 dp[i - 1]에서 [-1, 0, +1]에 포함 되는 값과 현재 값을 더하여 최대 값을 갱신하여 dp로 만든다.

코드

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

public class Main {
	static int n;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	n = stoi(br.readLine());
    	int[][] arr = new int[n][3];
    	
    	StringTokenizer stk;
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < 3; j++) {
    			arr[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
    	// 최대 점수를 찾기 위한 기본 세팅
    	int max_result = 0;
    	int[][] maxDp = new int[n][3];
    	for(int i = 0; i < 3; i++)
    		maxDp[0][i] = arr[0][i];
    	
    	// 최소 점수를 찾기 위한 기본 세팅
    	int MAX_VALUE = 987654321;
    	int min_result = MAX_VALUE;
    	
    	int[][] minDp = new int[n][3];
    	
    	for(int i = 0; i < n; i++)
    		Arrays.fill(minDp[i], MAX_VALUE);	
    	
    	for(int i = 0; i < 3; i++)
    		minDp[0][i] = arr[0][i];
    	
    	// dp 구하기 시작
    	// 두번째 행 부터 차례로 탐색
    	for(int i = 1; i < n; i++) {
    		// 그 행의 3개의 수를 dp로 갱신한다.
    		for(int j = 0; j < 3; j++) {
    			// 이전 행의 dp값에서 현재 arr의 값을 더해 최대 값을 dp로 갱신
    			for(int k = 0; k < 3; k++) {
    				// 이전 행에서 현재 값의 x 차이가 1칸 이하로만 떨어진 값만 더하여 dp로 비교한다.
    				if(Math.abs(j - k) <= 1) {
    					maxDp[i][j] = Math.max(maxDp[i][j], maxDp[i - 1][k] + arr[i][j]);
    					minDp[i][j] = Math.min(minDp[i][j], minDp[i - 1][k] + arr[i][j]);
    				}
    			}
    		}
    	}
    	
		// 마지막 행 3개 열 중에서 최대, 최소를 구한다. 이 값이 최대, 최소 점수이다.
    	for(int i = 0; i < 3; i++) {
    		max_result = Math.max(max_result, maxDp[n - 1][i]);
    		min_result = Math.min(min_result, minDp[n - 1][i]);
    	}
    
    	System.out.println(max_result);
    	System.out.println(min_result);

    	br.close();
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점