BEAKJOON / 백준 - JAVA 2096번 내려가기

2024.09.07기준 - 골드5

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 조건에 맞게 격자에서 내려갈 때 가장 작은 값과 큰 값을 출력하는 문제입니다.

다이나믹 프로그래밍으로 접근을 했습니다.

 

1. 입력받은 값들을 저장해줍니다.

// 수를 저장할 배열
int[][] grid = new int[n][3];

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

    for (int j = 0; j < 3; j++) {
        grid[i][j] = Integer.parseInt(st.nextToken());
    }
}

 

2. dp를 3차원 배열로 생성해 최댓값과 최솟값을 같이 계산을 해주었습니다.

// dp[][][0] = 최댓값, dp[][][1] = 최솟값
int[][][] dp = new int[n][3][2];

 

첫 번째 줄을 세팅해줍니다.

// 첫 줄 세팅
for (int i = 0; i < 3; i++) {
    dp[0][i][0] = grid[0][i]; 
    dp[0][i][1] = grid[0][i];
}

 

3. dp 계산

2번째 줄부터 윗 줄을 참조하면서

왼쪽은 (윗 줄 왼쪽), (윗 줄 가운데) 2개 중 비교를 해 더 해줍니다.

가운데는 (윗 줄 왼쪽), (윗 줄 가운데), (윗 줄 오른쪽) 3개 중 비교를 해 더 해줍니다.

오른쪽은 (윗 줄 가운데), (윗 줄 오른쪽) 2개를 비교를 해 더 해줍니다.

// 2번째 줄부터 윗 줄을 참조하며 가장 큰 값과 작은 값을 현재 값과 합쳐줍니다.
for (int i = 1; i < n; i++) {
    dp[i][0][0] = Math.max(dp[i - 1][0][0], dp[i - 1][1][0]) + grid[i][0];
    dp[i][1][0] = Math.max(dp[i - 1][0][0], Math.max(dp[i - 1][1][0], dp[i - 1][2][0])) + grid[i][1];
    dp[i][2][0] = Math.max(dp[i - 1][1][0], dp[i - 1][2][0]) + grid[i][2];

    dp[i][0][1] = Math.min(dp[i - 1][0][1], dp[i - 1][1][1]) + grid[i][0];
    dp[i][1][1] = Math.min(dp[i - 1][0][1], Math.min(dp[i - 1][1][1], dp[i - 1][2][1])) + grid[i][1];
    dp[i][2][1] = Math.min(dp[i - 1][1][1], dp[i - 1][2][1]) + grid[i][2];
}

 

4. 연산이 끝난 마지막 줄에 최댓값과 최솟값을 출력해줍니다.

int max = 0;
int min = 1000000; // 최솟값은 문제 범위 상 900000이 최대이기 때문에 1000000으로 설정.
for (int j = 0; j < 3; j++) {
    max = Math.max(max, dp[n - 1][j][0]);
    min = Math.min(min, dp[n - 1][j][1]);
}

// 출력
sb.append(max).append(" ").append(min);

 

 

코드

package Main;

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

public class Main {
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine()); // 줄의 개수
		
		// 수를 저장할 배열
		int[][] grid = new int[n][3];
		
		StringTokenizer st;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < 3; j++) {
				grid[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// dp[][][0] = 최댓값, dp[][][1] = 최솟값
		int[][][] dp = new int[n][3][2];
		
		// 첫 줄 세팅
		for (int i = 0; i < 3; i++) {
			dp[0][i][0] = grid[0][i]; 
			dp[0][i][1] = grid[0][i];
		}
		
		// 2번째 줄부터 윗 줄을 참조하며 가장 큰 값과 작은 값을 현재 값과 합쳐줍니다.
		for (int i = 1; i < n; i++) {
			dp[i][0][0] = Math.max(dp[i - 1][0][0], dp[i - 1][1][0]) + grid[i][0];
			dp[i][1][0] = Math.max(dp[i - 1][0][0], Math.max(dp[i - 1][1][0], dp[i - 1][2][0])) + grid[i][1];
			dp[i][2][0] = Math.max(dp[i - 1][1][0], dp[i - 1][2][0]) + grid[i][2];
			
			dp[i][0][1] = Math.min(dp[i - 1][0][1], dp[i - 1][1][1]) + grid[i][0];
			dp[i][1][1] = Math.min(dp[i - 1][0][1], Math.min(dp[i - 1][1][1], dp[i - 1][2][1])) + grid[i][1];
			dp[i][2][1] = Math.min(dp[i - 1][1][1], dp[i - 1][2][1]) + grid[i][2];
		}
		
		int max = 0;
		int min = 1000000; // 최솟값은 문제 범위 상 900000이 최대이기 때문에 1000000으로 설정.
		for (int j = 0; j < 3; j++) {
			max = Math.max(max, dp[n - 1][j][0]);
			min = Math.min(min, dp[n - 1][j][1]);
		}
		
		// 출력
		sb.append(max).append(" ").append(min);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}