[백준 - 2096] 내려가기 - Java

문제 설명

 

2096번: 내려가기

 

접근 방법

다이나믹 프로그래밍(메모이제이션 기법)을 통해 문제를 해결할 수 있었습니다.

 

어떻게 값을 메모이제이션 할 수 있을까 고민하던 중 그림으로 그려보다가 아이디어를 떠올릴 수 있었습니다.

 

 

위 그림을 통해 다음과 같은 사실을 알 수 있습니다.

 

• 세 개의 칸 중 왼쪽 칸의 값은 바로 위 칸의 값과 그 오른쪽 칸의 값에만 의존적입니다.
• 세 개의 칸 중 가운데 칸의 값은 위에 있는 세 개의 칸 값에 의존적입니다.
• 마지막으로, 세 개의 칸 중 오른쪽 칸의 값은 바로 위 칸의 값과 그 왼쪽 칸의 값에만 의존적입니다.

 

위 논리를 바탕으로 한 두 종류(최대, 최소)의 메모이제이션을 통해, 전체적인 내려가는 경로에 따른 합의 값에 대한 최댓값과 최솟값을 구할 수 있었습니다. 이에 대한 로직은 다음과 같습니다.

 

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

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

 

전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] board = new int[n][3];

        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            board[i][0] = Integer.parseInt(st.nextToken());
            board[i][1] = Integer.parseInt(st.nextToken());
            board[i][2] = Integer.parseInt(st.nextToken());
        }

        int[][] maxMemo = new int[n][3];
        int[][] minMemo = new int[n][3];

        maxMemo[0][0] = board[0][0];
        maxMemo[0][1] = board[0][1];
        maxMemo[0][2] = board[0][2];

        minMemo[0][0] = board[0][0];
        minMemo[0][1] = board[0][1];
        minMemo[0][2] = board[0][2];

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

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

        System.out.printf("%d %d",
            Math.max(maxMemo[n-1][0], Math.max(maxMemo[n-1][1], maxMemo[n-1][2])),
            Math.min(minMemo[n-1][0], Math.min(minMemo[n-1][1], minMemo[n-1][2]))
        );
    }
}

 

참고자료

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