백준 16639번: 괄호 추가하기 3 (Java)

접근

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

16639번: 괄호 추가하기 3

문제 힌트에서 다이나믹 프로그래밍(DP) 문제임을 확인하고 문제 풀이 진행하였다. DP임을 알고 문제를 다시 읽어보니 1+2+3 이라는 문제가 있을 때, (1+2)+3 으로 풀 수도 있고, 1+(2+3) 으로 풀 수도 있는데 이 과정에서 1+2와 2+3을 각각 dp에 저장하여 dp[i][j]에는 i부터 j까지 계산했을 때의 최대값을 저장할 수 있도록 일반화 하여 문제를 풀면 해결할 수 있겠다고 생각했다.

하지만 문제가 쉽게 해결되지 않았고, 다른 분들의 풀이를 보고 잘못된 점을 파악하였다.

가장 오판했던 점은 빼기 연산으로 인하여 중간에 음수 값이 나올 수 있고, 음수는 거의 대부분의 경우에 최대값이 되지 못한다. 하지만 음수 * 음수 는 양수 결과 값을 얻을 수 있고, 이 경우엔 최대값이 될 수도 있다. 즉 dp를 진행할 때, 최대값만 저장하면서 진행하면 안되고, 최소값도 동일하게 저장하면서 계산해야 하며, 다음 칸의 연산을 진행할 때, 이 최대값과 최소값을 이용하여 다음칸에 올 수 있는 최대값과 최소값을 정하면 된다.

참고한 풀이는 아래 링크 참조

https://gre-eny.tistory.com/318

[Java] 백준 16639 (괄호 추가하기 3) Gold 1

코드

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

public class Main {

  static int N, ans;
  static char[] input;
  static int[][] dp_min, dp_max;

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

    dp_min = new int[N][N];
    dp_max = new int[N][N];
    for (int i = 0; i < N; i++) {
      Arrays.fill(dp_min[i], Integer.MAX_VALUE);
      Arrays.fill(dp_max[i], Integer.MIN_VALUE);
    }
    for (int i = 0; i < N; i += 2) {
      dp_max[i][i] = input[i] - '0';
      dp_min[i][i] = input[i] - '0';
    }

    for (int j = 2; j < N; j += 2) {
      for (int i = 0; i < N - j; i += 2) {
        for (int k = 2; k <= j; k += 2) {
          char op = input[i + k - 1];
          int[] tmp = new int[4];
          tmp[0] = cal(dp_max[i][i + k - 2], dp_max[i + k][i + j], op);
          tmp[1] = cal(dp_max[i][i + k - 2], dp_min[i + k][i + j], op);
          tmp[2] = cal(dp_min[i][i + k - 2], dp_max[i + k][i + j], op);
          tmp[3] = cal(dp_min[i][i + k - 2], dp_min[i + k][i + j], op);
          Arrays.sort(tmp);
          dp_max[i][i + j] = Math.max(dp_max[i][i + j], tmp[3]);
          dp_min[i][i + j] = Math.min(dp_min[i][i + j], tmp[0]);
        }
      }
    }

    System.out.println(dp_max[0][N - 1]);
  }

  static int cal(int a, int b, char operator) {
    if (operator == '+') {
      return a + b;
    } else if (operator == '-') {
      return a - b;
    } else {
      return a * b;
    }
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!