[백준 - 1983번] 숫자 박스 - Java

문제 링크

https://www.acmicpc.net/problem/1983

문제

티어: 골드 2
알고리즘: dp

입력

첫 줄에는 숫자 박스의 열의 수를 나타내는 정수 N(1 ≤ N ≤ 400)이 주어진다. 그 다음 두 줄에는 각각 숫자 박스의 위와 아래의 행에 놓인 초기 숫자판들의 숫자가 하나 이상의 공백을 두고 나타나는데, 숫자판이 없는 빈칸은 0으로 표시된다. 단, 숫자판의 숫자는 모두 -10 이상 10 이하의 0이 아닌 정수이다.

출력

입력으로 주어진 숫자 박스의 각 행의 숫자판들을 가로로 이동시켜 얻을 수 있는 숫자 박스의 최댓값을 첫 번째 줄에 출력한다.

풀이

각 행의 숫자판들을 가로로 이동시켜 얻을 수 있는 숫자 박스의 최댓값을 출력해야 한다.
문제에서 중요한 정보는 숫자의 순서는 그대로 유지한채 빈칸은 이동할 수 있다는 것이다.
이를 재해석하면 빈칸은 어디로든 움직일 수 있다는 것이다. 이를 인지하는게 중요하다.

0은 어디로든 이동할 수 있기 때문에 첫 번째 행에서 첫 번째 열로 이동할 수 있다.
두 번째 행 또한 마찬가지다.

그러면 케이스를 다음과 같이 4가지로 나눠줄 수 있다.

• 첫 번재 행의 첫 번째 열에 0이 오지 않는 경우, 두 번재 행의 첫 번째 열에 0이 오지 않는 경우
• 첫 번재 행의 첫 번째 열에 0이 오지 않는 경우, 두 번재 행의 첫 번째 열에 1이 오는 경우
• 첫 번재 행의 첫 번째 열에 1이 오는 경우, 두 번재 행의 첫 번째 열에 0이 오지 않는 경우
• 첫 번재 행의 첫 번째 열에 1이 오는 경우, 첫 번재 행의 첫 번째 열에 1이 오는 경우

그래서 dp[A][B][C] 는
A는 열 번호,
B는 첫 번째 행에서 1번 열부터 ~ A열까지 0의 개수,
C는 두 번째 행에서 1번 열부터 ~ B열까지 0의 개수
로 정의해 줄 수 있다.

이후에는 dp[1][0][0] 부터 dp[N][A수열의 총 0의 개수][B수열의 총 0의 개수]까지 반복하면서
각 경우를 위 4가지 케이스를 적용해 MAX값을 찾으면 된다.

이 풀이의 시간 복잡도는 O(N^3)이다.

소스 코드

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

public class Main {
    static final int[] ac = {0, 0, 1, 1};
    static final int[] bc = {0, 1, 0, 1};
    static int N, AZC, BZC;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      ArrayList<Integer> A = new ArrayList<>();
      ArrayList<Integer> B = new ArrayList<>();
      AZC = fill(br.readLine(), A);
      BZC = fill(br.readLine(), B);
      int[][][] dp = new int[N + 1][AZC + 1][BZC + 1];
      init(dp);
      for(int i=1; i<=N; i++) {
          for(int j=0; j<=AZC; j++) {
              if(i < j) {
                  break;
              }
              for(int k=0; k<=BZC; k++) {
                  if(i < k) {
                      break;
                  }
                  for(int l=0; l<4; l++) {
                      if(j - ac[l] < 0 || k - bc[l] < 0) {
                          break;
                      }
                      int v = 0;
                      if(l == 0) {
                         v = A.get(i - (j - ac[l])) * B.get(i - (k - bc[l]));
                      }
                      dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - ac[l]][k -bc[l]] + v);
                  }
              }
          }
      }
      System.out.println(dp[N][AZC][BZC]);
  }
  
  static void init(int[][][] dp) {
      for(int i=1; i<dp.length; i++) {
          for(int j=0; j<dp[i].length; j++) {
              for(int k=0; k<dp[i][j].length; k++) {
                  dp[i][j][k] = -1000000;
              }
          }
      }
  }
  
  static int fill(String input, ArrayList<Integer> list) {
      list.add(0);
      int zCout = 0;
      StringTokenizer st = new StringTokenizer(input);
      for(int i=0; i<N; i++) {
          int n = Integer.parseInt(st.nextToken());
          if(n == 0) {
              zCout += 1;
          } else {
              list.add(n);
          }
      }
      for(int i=1; i<=zCout; i++) {
          list.add(0);
      }
      return zCout;
  }
}