문제

이해

Nx3 보드의 각 칸에는 숫자가 적혀 있다. 보드에서 내려가기 게임을 하려고 한다.

내려가기 게임의 규칙은 단순하다. 현재 위치에서 다음 행의 칸으로 내려가되 현재 열과 인접한 칸만 가능하다.

예를 들어 1열에 있다면 다음 칸에는 0열, 1열, 2열 모두 가능하지만 0열에 있다면 다음 칸에는 0열, 1열만 가능하다.

위 규칙으로 게임을 진행했을 때 얻을 수 있는 점수의 최대, 최소를 구하여라.

접근

처음에 NxN 보드인 줄 알기도 하고 N이 100,000까지인데 dp 배열 변수를 만들려고 했다.

당연하게도 메모리 초과가 발생했다..

N의 범위로 인해 dp배열 크기를 극단적으로 줄여야 하는데 방법이 떠오르지 않아서 검색을 해보았다.

결론부터 말하자면 이 문제는 슬라이딩 윈도우를 사용해서 dp의 배열 크기를 줄일 수 있다.

슬라이딩 윈도우는 네트워크에서만 들어봐서 어떻게 적용해야할지 몰랐는데 다음 블로그 포스팅을 보고 이해할 수 있었다.

백준 2096

요약하자면 보드는 Nx3이며 항상 3개의 수를 받기 때문에 슬라이딩 윈도우의 크기를 3으로 하고 3개의 수를 입력받을 때마다 윈도우 내부의 값들을 갱신하면 되는 것이었다.

갱신하기 위해서는 규칙을 주의해야 한다. 다음 행의 칸을 선택하는 기준은 인접한 열이여야 한다.

이는 반대로 입력된 숫자 입장에서 이전 행의 인접한 열에서만 접근 가능하다는 것을 의미한다.

위처럼 (1, 1)칸에서 값을 입력받았을 때 dp[0]의 값을 Max(dp[0], dp[1]) + input 과 같이 갱신할 수 있는 것이다.

이 과정을 모든 행이 입력될 때까지 반복하면 최종적으로 dp에는 마지막 행에 도달된 최대값, 최소값 집합이 저장된다.

코드

package java_baekjoon;

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

public class prob2096_2 {
  static int N;
  static int[] d_col = { -1, 0, 1 };
  static int[] board;
  static int[] max_dp;
  static int[] min_dp;
  static int max = Integer.MIN_VALUE;
  static int min = Integer.MAX_VALUE;

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

    N = Integer.parseInt(br.readLine());
    board = new int[3];
    max_dp = new int[3];
    min_dp = new int[3];

    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int v0 = Integer.parseInt(st.nextToken());
      int v1 = Integer.parseInt(st.nextToken());
      int v2 = Integer.parseInt(st.nextToken());

      if (i == 0) {
        max_dp[0] = min_dp[0] = v0;
        max_dp[1] = min_dp[1] = v1;
        max_dp[2] = min_dp[2] = v2;
      } else {
        int buf_max_dp_0 = max_dp[0];
        int buf_max_dp_2 = max_dp[2];
        max_dp[0] = Math.max(max_dp[0], max_dp[1]) + v0;
        max_dp[2] = Math.max(max_dp[1], max_dp[2]) + v2;
        max_dp[1] = Math.max(Math.max(buf_max_dp_0, max_dp[1]), buf_max_dp_2) + v1;

        int buf_min_dp_0 = min_dp[0];
        int buf_min_dp_2 = min_dp[2];
        min_dp[0] = Math.min(min_dp[0], min_dp[1]) + v0;
        min_dp[2] = Math.min(min_dp[1], min_dp[2]) + v2;
        min_dp[1] = Math.min(Math.min(buf_min_dp_0, min_dp[1]), buf_min_dp_2) + v1;
      }
    }

    max = Math.max(Math.max(max_dp[0], max_dp[1]), max_dp[2]);
    min = Math.min(Math.min(min_dp[0], min_dp[1]), min_dp[2]);

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

결과