[백준/Java] 2096번 : 내려가기

✏️ 문제 분석

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

N개의 줄에 숫자가 세 개씩 주어지고, 세 개 중 하나를 고르면서 아래로 내려가는 게임을 한다.

다음 줄의 숫자로 내려갈 때는, 바로 아래 또는 바로 아래와 인접한 수로만 내려갈 수 있다.

얻을 수 있는 최대 점수, 최소 점수를 구하여라.

✏️ 구현 아이디어

3
1 2 3
4 5 6
4 9 0

 

숫자표를 이차원 배열 dp라고 했을 때, 

두 번째 줄 이상(n>0)에서 다음과 같은 규칙이 적용된다.

• dp[n][0]은 dp[n-1][0], dp[n-1][1]
• dp[n][1]은 dp[n-1][0], dp[n-1][1], dp[n-1][2]
• dp[n][2]은 dp[n-1][1], dp[n-1][2]

로부터 내려올 수 있다.

---

dp[0][0]	dp[0][1]	dp[0][2]
dp[1][0]

예를 들어 dp[1][0]은 dp[0][0], dp[0][1]로부터 내려올 수 있다.

만약 최대 점수를 구하는 중이라면 둘 중 더 큰 숫자를,

최소 점수를 구하는 중이라면 더 작은 숫자를 dp[1][0]에 더해서 dp[1][0]값을 갱신한다.

 

최대 점수 : dp[1][0] + max(dp[0][0], dp[0][1])
최소 점수 : dp[1][0] + min(dp[0][0], dp[0][1])

 

dp[0][0]	dp[0][1]	dp[0][2]
	dp[1][1]

마찬가지로 dp[1][1]은 dp[0][0], dp[0][1], dp[0][2]로부터 내려올 수 있다.

 

최대 점수 : dp[1][1] + max(dp[0][0], dp[0][1], dp[0][2])
최소 점수 : dp[1][1] + min(dp[0][0], dp[0][1], dp[0][2])

 

dp[0][0]	dp[0][1]	dp[0][2]
		dp[1][2]

최대 점수 : dp[1][2] + max(dp[0][1], dp[0][2])
최소 점수 : dp[1][2] + min(dp[0][1], dp[0][2])

 

이런 방식으로 n-1행까지 수행한다. (단, 최댓값, 최솟값을 별도의 배열로 구함)

✏️ 알고리즘

이전에 구했던 답을 다음 문제를 푸는 데 사용하는 방법이므로, dp를 사용하는 것이 적절하다.

✏️ 시간 복잡도

dp는 모든 노드를 한 번만 방문하므로 시간 복잡도가 O(N)이다. 

노드는 최대 100,000개이므로 시간 제한(1초) 안에 모두 연산할 수 있다.

✏️ 코드 설계

1. 값 입력받기
2. 최대값, 최소값 구할 이차원 배열 dpMax, dpMin 각각 선언
3. 두 번째 행부터 좌표당 findMax(), findMin() 수행
   1. 0열 : 이전 행의 0, 1열 중 최대/최솟값 + 현재값
   2. 1열 : 이전 행의 0, 1, 2열 중 최대/최솟값 + 현재값
   3. 2열 : 이전 행의 1, 2열 중 최대/최솟값 + 현재값
   4. 을 누적한다.
4. dpMax, dpMin의 n-1행을 정렬한 후, 최대/최솟값을 각각 출력

✏️ 정답 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int[][] dpMax, dpMin;
    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());

        dpMax = new int[n][3];
        dpMin = new int[n][3];
        for(int i = 0; i< n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<3; j++){
                int val = Integer.parseInt(st.nextToken());
                dpMax[i][j] = dpMin[i][j] = val;
            }
        }

        for(int i = 1; i< n; i++){
            dpMax[i][0] += Math.max(dpMax[i-1][0], dpMax[i-1][1]);
            dpMax[i][1] += Math.max(Math.max(dpMax[i-1][0], dpMax[i-1][1]), dpMax[i-1][2]);
            dpMax[i][2] += Math.max(dpMax[i-1][1], dpMax[i-1][2]);

            dpMin[i][0] += Math.min(dpMin[i-1][0], dpMin[i-1][1]);
            dpMin[i][1] += Math.min(Math.min(dpMin[i-1][0], dpMin[i-1][1]), dpMin[i-1][2]);
            dpMin[i][2] += Math.min(dpMin[i-1][1], dpMin[i-1][2]);
        }
        Arrays.sort(dpMax[n-1]);
        Arrays.sort(dpMin[n-1]);
        System.out.println(dpMax[n-1][2] + " " + dpMin[n-1][0]);

    }


}