[백준] 2096번: 내려가기 (C++, JAVA)

문제 링크

2096번: 내려가기

서론

요즘들어 DP 문제를 풀지 않아서 푸는 방법을 잊고 살고 있었습니다.

백준 문제집을 훑어보다가 좋은 DP문제가 있기에 풀어보게 되었습니다. 😄

풀이

문제에서 친절하게 그림으로 설명하듯이, 2*3칸의 구성을 잘 이용해야 합니다. 단순한 DP 풀이를 한 다음, 문제에서 주어진 메모리 제한이 \(4MB\) 여서 메모이제이션 배열의 크기가 일정 이상 커지면 메모리 초과가 발생하기 때문에 메모리 최적화 과정을 거쳐야 문제를 풀이할 수 있게 됩니다.

DP 풀이 과정을 우선 설명해 드리겠습니다.

문제에서 주어진 그림

문제에서는 위 그림과 같이 맨 왼쪽에 있을 경우 왼쪽과 가운데, 가운데에 있을 경우 모든 구역, 맨 오른쪽에 있을 경우 오른쪽과 가운데를 다음에 지나갈 수 있도록 했습니다. 그리고 지나가는 구역들의 모든 합을 구해야 합니다. 여기서 떠오르는 사실이 있습니다. 바로 누적 합입니다. 위 그림을 상하반전으로 뒤집어보겠습니다.

상하반전한 그림

거꾸로 생각해보면, 더해진 후의 다음 값이 나오기 위해서는 그 전에도 문제에서 주어진 지나가는 방법의 루트를 그대로 따라와야 합니다. 결국 루트는 정해져 있기 때문에, 정해져 있는 루트를 따라 누적합을 진행하면 답을 얻을 수 있습니다.

정리하자면, 위 상하반전한 그림의 패턴으로 누적합을 진행하면 원하는 최대값과 최소값을 얻을 수 있습니다.

따라서 위 그림과 같이 그대로 진행하여 DP를 작성해보면 다음과 같은 식이 나옵니다.

\[\begin{aligned} dp[i][1] &= minormax(dp[i - 1][1] + arr[i][1], dp[i - 1][2] + arr[i][1]) \\ dp[i][2] &= minormax(dp[i - 1][1] + arr[i][2], dp[i - 1][2] + arr[i][2], dp[i - 1][3] + arr[i][2])) \\ dp[i][3] &= minormax(dp[i - 1][2] + arr[i][3], dp[i - 1][3] + arr[i][3]) \end{aligned}\]

아래 더보기는 위 풀이를 종합해서 제출해본 C++ 코드입니다. 무작정 모든 과정과 모든 수를 저장해놓고 DP를 진행했기 떄문에 메모리 초과가 났습니다.

// C++ 코드 (메모리 초과)
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int arr[100001][4];
int dp[100001][4];

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 3; j++) {
      cin >> arr[i][j];
    }
  }

  for (int i = 1; i <= n; i++) {
    dp[i][1] = max(dp[i - 1][1] + arr[i][1], dp[i - 1][2] + arr[i][1]);
    dp[i][2] = max(dp[i - 1][1] + arr[i][2], max(dp[i - 1][2] + arr[i][2], dp[i - 1][3] + arr[i][2]));
    dp[i][3] = max(dp[i - 1][2] + arr[i][3], dp[i - 1][3] + arr[i][3]);
  }

  int maxVal = *max_element(dp[n] + 1, dp[n] + 4);
  
  for (int i = 1; i <= n; i++) {
    dp[i][1] = min(dp[i - 1][1] + arr[i][1], dp[i - 1][2] + arr[i][1]);
    dp[i][2] = min(dp[i - 1][1] + arr[i][2], min(dp[i - 1][2] + arr[i][2], dp[i - 1][3] + arr[i][2]));
    dp[i][3] = min(dp[i - 1][2] + arr[i][3], dp[i - 1][3] + arr[i][3]);
  }
  
  int minVal = *min_element(dp[n] + 1, dp[n] + 4);

  cout << maxVal << ' ' << minVal;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  solve();
  return 0;
}

메모리 초과를 해결하려면, 모든 경우의 수를 저장하지 않고 진행하면 됩니다. 생각해보면 결국 합을 계산하는데 있어 필요한 부분은 더할 값(`arr[3]`), 더하기 이전의 값과 더한 후의 값(`dp[2][4]`)이 연산에만 쓰이기 때문에, 이것만을 고려해서 DP를 진행하면 메모리초과를 해결할 수 있게 됩니다.

풀이코드

C++ 풀이코드

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

#define endl "\n"

int arr[4];
int maxDP[2][4];
int minDP[2][4];

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 3; j++) {
      cin >> arr[j];
      maxDP[0][j] = maxDP[1][j];
      minDP[0][j] = minDP[1][j];
    }
    
    maxDP[1][1] = max(maxDP[0][1] + arr[1], maxDP[0][2] + arr[1]);
    maxDP[1][2] = max(maxDP[0][1] + arr[2], max(maxDP[0][2] + arr[2], maxDP[0][3] + arr[2]));
    maxDP[1][3] = max(maxDP[0][2] + arr[3], maxDP[0][3] + arr[3]);

    minDP[1][1] = min(minDP[0][1] + arr[1], minDP[0][2] + arr[1]);
    minDP[1][2] = min(minDP[0][1] + arr[2], min(minDP[0][2] + arr[2], minDP[0][3] + arr[2]));
    minDP[1][3] = min(minDP[0][2] + arr[3], minDP[0][3] + arr[3]);
  }
  int maxVal = *max_element(maxDP[1] + 1, maxDP[1] + 4);
  int minVal = *min_element(minDP[1] + 1, minDP[1] + 4);

  cout << maxVal << ' ' << minVal;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  solve();
  return 0;
}

Java 풀이코드

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

class Main {

    private static int[] arr = new int[4];
    private static int[][] maxDP = new int[2][4];
    private static int[][] minDP = new int[2][4];

    private static void solve(BufferedReader br) throws IOException {
        int n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) {
            String[] inp = br.readLine().split(" ");
            for (int j = 1; j <= 3; j++) {
                arr[j] = Integer.parseInt(inp[j - 1]);
                maxDP[0][j] = maxDP[1][j];
                minDP[0][j] = minDP[1][j];
            }

            maxDP[1][1] = Math.max(maxDP[0][1] + arr[1], maxDP[0][2] + arr[1]);
            maxDP[1][2] = Math.max(maxDP[0][1] + arr[2], Math.max(maxDP[0][2] + arr[2], maxDP[0][3] + arr[2]));
            maxDP[1][3] = Math.max(maxDP[0][2] + arr[3], maxDP[0][3] + arr[3]);

            minDP[1][1] = Math.min(minDP[0][1] + arr[1], minDP[0][2] + arr[1]);
            minDP[1][2] = Math.min(minDP[0][1] + arr[2], Math.min(minDP[0][2] + arr[2], minDP[0][3] + arr[2]));
            minDP[1][3] = Math.min(minDP[0][2] + arr[3], minDP[0][3] + arr[3]);
        }
        int maxVal = 0, minVal = Integer.MAX_VALUE;
        for (int i = 1; i <= 3; i++) {
            maxVal = Math.max(maxVal, maxDP[1][i]);
            minVal = Math.min(minVal, minDP[1][i]);
        }
        res.append(maxVal).append(' ').append(minVal);
    }

    private static StringBuilder res;
    public static void main(String args[]) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            res = new StringBuilder();
            solve(br);
            bw.write(res.toString());
        }
    }
}

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!