[백준] 2096 내려가기 - JAVA

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

2096번: 내려가기

 

 

[알고리즘]

• DP
• 다음 줄로 이동하면서 각 위치에서의 최대 점수, 최소 점수를 저장한다. 
• 최종적으로 N개의 줄을 모두 이동했을 때, 마지막 줄에 저장되어 있는 최대 최소값 반환 
• 두개의 DP 2차원 배열을 생성하여 최댓값/ 최솟값 따로 저장 
• dp[i][j] = (i,j) 위치에서 얻을 수 있는 최대 or 최소 점수 

---

 

[설계]

• 한줄에 숫자가 3개씩만 있기 때문에 각 위치에 대해 조건을 나누어 dp 값을 구한다. 
  1. dp[i][0] = dp[i-1][0], dp[i-1][1] 중 max/min + map[i][0] 
  2. dp[i][1] = dp[i-1][0], dp[i-1][1], dp[i-1][2] 중 max/min + map[i][0] 
  3. dp[i][2] = dp[i-1][1], dp[i-1][2] 중 max/min + map[i][0] 

---

 

[구현 과정]

• dp_max[i][j] : (i,j) 위치에서 얻을 수 있는 최대 점수 
• dp_min[i][j] : (i,j) 위치에서 얻을 수 있는 최소 점수  

 

1. 주어진 N개의 줄을 입력받아 int형 2차원 배열 map 에 저장.
   (첫번째 줄에 대한 조건을 따로 두지 않기 위해 가장 윗줄에 한줄 추가하여 0으로 채움 )

 

2. 각 열마다 불러올 수 있는 dp값을 비교하여 max or min 값에 현재 값을 더해주며 dp 배열을 채운다.

 

3. dp_max 배열의 최댓값, dp_min 배열의 최솟값을 출력. 

 

---

 

[소스 코드 1]

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

public class Main {
	static int N;
	static int[][] map; 
	static int[][] dp_max; 
	static int[][] dp_min; 
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		
		map = new int[N+1][3];
		dp_max = new int[N+1][3];
		
		dp_min = new int[N+1][3];
	
		for(int i=1; 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=1; i<=N; i++) {
			for(int j=0; j<3; j++) {
				if(j==0) dp_max[i][j]= Math.max(dp_max[i-1][0], dp_max[i-1][1])+map[i][j]; 	
				
				else if(j==1) {
					dp_max[i][j]= Math.max(dp_max[i-1][0], Math.max(dp_max[i-1][1], dp_max[i-1][2]))+map[i][j];
				}
				
				else dp_max[i][j]=Math.max(dp_max[i-1][1], dp_max[i-1][2])+map[i][j]; 
			}
		}
		
		for(int i=1; i<=N; i++) {
			for(int j=0; j<3; j++) {
				if(j==0) dp_min[i][j]= Math.min(dp_min[i-1][0], dp_min[i-1][1])+map[i][j]; 	
				
				else if(j==1) {
					dp_min[i][j]= Math.min(dp_min[i-1][0], Math.min(dp_min[i-1][1], dp_min[i-1][2]))+map[i][j];
				}
				
				else dp_min[i][j]=Math.min(dp_min[i-1][1], dp_min[i-1][2])+map[i][j]; 
			}
		}
		
		int max= Math.max(dp_max[N][0], Math.max(dp_max[N][1], dp_max[N][2]));
		int min= Math.min(dp_min[N][0], Math.min(dp_min[N][1], dp_min[N][2]));
		System.out.println(max+" "+min);

	}//end of main 
}//end of class

 

 

[소스 코드 2]

• DP 1차원 배열 + 슬라이딩 윈도우 기법
• 1차원 dp배열에 값을 갱신하면서 저장하는 것이므로, 변하는 값을 따로 변수에 저장해두는 것만 주의하면 된다, 
  (ex) dp_max[0] 연산 후, 바뀐 dp_max[0]으로 dp_max[1] 구하면 오류, before_0 변수에 이전 값 저장) 

 

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

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] map = new int[N][3];
		int[] dp_max = new int[3];
		int[] dp_min = new int[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_max[i]= dp_min[i] = map[0][i]; 
		}
		
		for(int i=1; i<N; i++) {
			int before_0 = dp_max[0] , before_2 = dp_max[2]; 
			dp_max[0] = Math.max(dp_max[0], dp_max[1]) +map[i][0]; 
			dp_max[2] = Math.max(dp_max[1], dp_max[2]) +map[i][2]; 
			dp_max[1] = Math.max(before_0, Math.max(dp_max[1], before_2)) +map[i][1]; 
			
			before_0 = dp_min[0] ; before_2 = dp_min[2]; 
			dp_min[0] = Math.min(dp_min[0], dp_min[1]) +map[i][0]; 
			dp_min[2] = Math.min(dp_min[1], dp_min[2]) +map[i][2]; 
			dp_min[1] = Math.min(before_0, Math.min(dp_min[1], before_2)) +map[i][1]; 
		}
		
		int max= Math.max(dp_max[0], Math.max(dp_max[1], dp_max[2]));
		int min= Math.min(dp_min[0], Math.min(dp_min[1], dp_min[2]));
		System.out.println(max+" "+min);
	
	}//end of main 
}//end of class