[백준] 2096번 - 내려가기 [Java][C++]

문제 링크

---

1. 문제 풀이

내려가기 게임에서 이동 가능한 경로는 현재 위치에서 바로 아래 칸이거나 대각선 칸으로만 이동할 수 있다. $0$ 번 인덱스 위치에서는 $0$, $1$ 번 인덱스로, $1$ 번 인덱스 위치에서는 $0$, $1$, $2$ 번 인덱스로, $2$ 번 인덱스 위치에서는 $1$, $2$ 번 인덱스로 이동할 수 있다. 이때 얻을 수 있는 점수의 최댓값과 최솟값을 구해야 하며 풀이 언어에 따라 다르지만 4MB 의 메모리 제한이 있다. 메모리 효율적으로 이 문제를 해결하는데는 다이나믹 프로그래밍과 토글링 기법을 활용하면 된다.

다이나믹 프로그래밍의 경우 현재 위치로 올 수 있었던 이전 위치까지의 점수의 최댓값, 최솟값에서 현재 위치의 값을 더하는 것을 반복하는 것으로 점화식을 세울 수 있다. 예제 입력 1에 대해서 아래와 같은 과정을 통해 dp 테이블을 만들 수 있다.

왼쪽은 주어진 입력, 오른쪽은 동일한 크기의 dp 테이블이다.

첫 행은 이전에 방문한 곳이 없으므로 현재 칸을 방문할 때 점수와 동일하다.

두 번째 행부터는 이전에 올 수 있었던 점수의 최댓값, 최솟값에서 현재 칸의 점수를 더하면 된다. 이전에 올 수 있었던 점수의 최댓값, 최솟값은 dp 테이블에 기록하고 있었으므로 해당 정보를 활용한다. 아래부터는 최댓값을 구하는 예시다.

최솟값 역시 동일하게 구하면 된다.

여기서 dp 테이블의 갱신에 이전 행의 정보만 필요하다는 점에서 임시 배열을 사용하거나 토글링 기법을 활용하면 메모리를 훨씬 더 절약할 수 있다.

임시 공간에 현재 갱신될 정보를 저장한 후 dp에 반영해주는 것을 반복하면 된다.

---

2. 코드

1. 다이나믹 프로그래밍 [Java]

prev 와 cur 을 포인터로 두는 토글링 대신 좀 더 간단하게 임시 배열을 활용했다.

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));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] maxDp = new int[3];
        int[] minDp = new int[3];
        int[] tmp = new int[3];  // 계산값 임시저장용 배열

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int x3 = Integer.parseInt(st.nextToken());

            // 최대 점수 계산
            tmp[0] = Math.max(maxDp[0], maxDp[1]) + x1;
            tmp[1] = Math.max(maxDp[0], Math.max(maxDp[1], maxDp[2])) + x2;
            tmp[2] = Math.max(maxDp[1], maxDp[2]) + x3;

            maxDp[0] = tmp[0];
            maxDp[1] = tmp[1];
            maxDp[2] = tmp[2];

            // 최소 점수 계산
            tmp[0] = Math.min(minDp[0], minDp[1]) + x1;
            tmp[1] = Math.min(minDp[0], Math.min(minDp[1], minDp[2])) + x2;
            tmp[2] = Math.min(minDp[1], minDp[2]) + x3;

            minDp[0] = tmp[0];
            minDp[1] = tmp[1];
            minDp[2] = tmp[2];
        }

        int max = Math.max(maxDp[0], Math.max(maxDp[1], maxDp[2]));
        int min = Math.min(minDp[0], Math.min(minDp[1], minDp[2]));

        System.out.println(max + " " + min);
    }
}

2. 다이나믹 프로그래밍 [C++]

prev 와 cur 을 포인터로 두는 토글링 대신 좀 더 간단하게 임시 배열을 활용했다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> mx_dp(3);
    vector<int> mn_dp(3);
    vector<int> tmp(3);  // 계산값 임시저장용 배열

    for (int i = 0; i < n; i++) {
        int x1, x2, x3;
        cin >> x1 >> x2 >> x3;

        // 최대 점수 계산
        tmp[0] = max(mx_dp[0], mx_dp[1]) + x1;
        tmp[1] = max({mx_dp[0], mx_dp[1], mx_dp[2]}) + x2;
        tmp[2] = max(mx_dp[1], mx_dp[2]) + x3;

        mx_dp[0] = tmp[0];
        mx_dp[1] = tmp[1];
        mx_dp[2] = tmp[2];

        // 최소 점수 계산
        tmp[0] = min(mn_dp[0], mn_dp[1]) + x1;
        tmp[1] = min({mn_dp[0], mn_dp[1], mn_dp[2]}) + x2;
        tmp[2] = min(mn_dp[1], mn_dp[2]) + x3;

        mn_dp[0] = tmp[0];
        mn_dp[1] = tmp[1];
        mn_dp[2] = tmp[2];
    }

    cout << max({mx_dp[0], mx_dp[1], mx_dp[2]}) << ' ' << min({mn_dp[0], mn_dp[1], mn_dp[2]});
}

---

3. 풀이 정보

1. 다이나믹 프로그래밍 [Java]

언어	시간	메모리	코드 길이
Java 11	372 ms	42220 KB	1517 B

2. 다이나믹 프로그래밍 [C++]

언어	시간	메모리	코드 길이
C++ 17	16 ms	2020 KB	985 B

---