[백준] 2096 내려가기 - DP JAVA

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

2096번: 내려가기

코드설명

DP 문제입니다.

 

DP[0][0~2] 까지는 먼저 선언해줍니다.

DP[1][0, 1, 2] 에서 각각 DP[1][0,1,2]에 올 수 있는 위치들의 최대값, 최솟값들을 구해서 진행하면됩니다.

 

 

대각선끼리 최대값을 잘 구하는지 체크해볼 좋은 예시가 있어서 가져왔습니다. https://www.acmicpc.net/board/view/4843

3
1 0 0
0 1 0
0 0 1

answer:
3 0


maxDP[][]
 1 0 0
 1 2 0
 2 2 3
 
 minDP[][]
 1 0 0
 0 1 0
 0 0 1

 

 

 

처음에 아래와 같이 min값을 잘못가져와서 틀렸습니다. 변수이름을 명확히 지어야할 것 같습니다.

for(int i=0;i<3;i++) {
    //answerMin = Math.min(dp[N-1][i], answer);  // 여기서 answer이 아닌 answerMin 이어야합니다
    answerMin = Math.min(dp[N-1][i], answerMin);  // 여기서 answer이 아닌 answerMin 이어야합니다
}

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int N;
	public static int answer = 0, answerMin = Integer.MAX_VALUE;
	public static int[][] map;
	public static int[][] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new int[N][3];
    	dp = new int[N][3];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0; j<3;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=0;i<3;i++) {
    		dp[0][i] = map[0][i];	
    	}
    	
    	for(int i=1; i<N;i++) {
    		
    		for(int j=0;j<3;j++) {
    			if(j == 0) {
    				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j+1]) + map[i][j];	
    			}
    			else if(j == 2) {
    				dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + map[i][j];
    			}else {
    				dp[i][j] = Math.max(dp[i-1][j-1], Math.max(dp[i-1][j], dp[i-1][j+1])) + map[i][j];
    			}
    				
    		}
    		
    	}
    	
    	for(int i=0;i<3;i++) {
    		answer = Math.max(dp[N-1][i], answer); 
    	}
    	
    	dp = new int[N][3];
    	for(int i=0;i<3;i++) {
    		dp[0][i] = map[0][i];	
    	}
    	for(int i=1; i<N;i++) {
    		
    		for(int j=0;j<3;j++) {
    			if(j == 0) {
    				dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j+1]) + map[i][j];	
    			}
    			else if(j == 2) {
    				dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + map[i][j];
    			}else {
    				dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i-1][j+1])) + map[i][j];
    			}
    		}
    		
    	}
    	
    	for(int i=0;i<3;i++) {
    		answerMin = Math.min(dp[N-1][i], answerMin); 
    	}
    	
    	System.out.println(answer+" "+answerMin);
    }
}