16639번: 괄호 추가하기 3

Skele·2025년 2월 14일

algorithm dynamic programming

알고리즘 문제 풀이

목록 보기

3/21

16639번: 괄호 추가하기 3

수식의 길이 N(1 ≤ N ≤ 19)가 홀수로 주어진다.
수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다.
문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다.
연산자는 +, -, * 중 하나이다.
괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 찾아라.
정답의 범위는 Integer 범위 이내이다.

접근

수식의 최대값

"수식의 최대값을 찾는 것 = 구간의 최대값을 찾는것" 이라고 볼 수 있다.
예를 들어 1+3+2 라는 수식이 있을 때 각 숫자를 0~2번이라고 설정하고 이차원 배열을 만든다.
배열의 [i][j]를 i번째 부터 j번째 숫자를 쓰는 수식의 최대값이라고 생각하면, [i][j]의 최대값은 i번째와 j번째 사이 구간들의 최대값들로부터 연산할 수 있다.

	0	1	2
0	1	4	6
1		3	5
2			2

추가길이가 1인 0~1 구간의 최대값 : dp[0][1] = Max(초기값, dp[0][0] + dp[1][1])
추가길이가 1인 1~2 구간의 최대값 : dp[1][2] = Max(초기값, dp[1][1] + dp[2][2])
추가길이가 2인 0~2 구간의 최대값 : dp[0][2] = Max(dp[0][0] + dp[1][2], dp[0][1] + dp[2][2])

음수값의 처리

덧셈 연산만 있다면, 이차원 배열 하나로 구간의 Max값을 계산하면 된다.
하지만 뺄셈 연산이 있다면 1-2-3 같은 경우, 1-(-1) 식으로 최소값을 뺄 때 최대값이 된다.
따라서, 최대값을 저장하는 이차원 배열 외에 최소값을 저장하는 이차원 배열 또한 필요하다.

곱셈의 처리

곱셈의 경우도 음수와 음수를 곱하면 양수가 되는 경우, 음수와 양수를 곱하면 음수가 되는 경우 등 경우의 수가 다양하다.
따라서 모든 경우의 수 중에서 최대값과 최소값을 선택해야한다.

코드

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    input(in);
    solve();
  }
  
  static int length;
  static int[] nums;
  static char[] ops;
  public static void input(BufferedReader in) throws IOException {
    length = Integer.parseInt(in.readLine());
    nums = new int[length/2+1];
    ops = new char[length/2];
    char[] line = in.readLine().toCharArray();
    for(int i = 0; i < length; i++) {
      if(i%2 == 0) {
        nums[i/2] = Character.getNumericValue(line[i]);
      } else {
        ops[i/2] = line[i];
      }
    }
  }
  
  public static void solve() {
    int[][] dp = new int[nums.length][nums.length]; //최대값 배열
    int[][] dpMin = new int[nums.length][nums.length]; //최소값 배열
    
    // 초기값 설정
    for(int i = 0; i < nums.length; i++) {
      for(int j = 0; j < nums.length; j++) {
        if(i == j) {
          dp[i][i] = nums[i];
          dpMin[i][j] = nums[i];
        } else {
          dp[i][j] = Integer.MIN_VALUE;
          dpMin[i][j] = Integer.MAX_VALUE;
        }
      }
    }
    
    for(int m = 1; m <= nums.length; m++) { // m = 추가길이
      for(int i = 0; i+m < nums.length; i++) { // i = 시작점
        for(int j = i; j < i+m; j++) { // j = 중간점
          char op = ops[j];
          int val = Integer.MIN_VALUE;
          int valMin = Integer.MAX_VALUE;
          switch(op) {
            case '+' : 
              val = Math.max(val, dp[i][j] + dp[j+1][i+m]);
              valMin = Math.min(valMin, dpMin[i][j] + dpMin[j+1][i+m]);
              break;
            case '-' : 
              val = Math.max(val, dp[i][j] - dpMin[j+1][i+m]);
              valMin = Math.min(valMin, dpMin[i][j] - dp[j+1][i+m]);
              break;
            default : 
              int[] arrMul = { 
	              dp[i][j] * dp[j+1][i+m], 
                dp[i][j] * dpMin[j+1][i+m], 
                dpMin[i][j] * dp[j+1][i+m], 
                dpMin[i][j] * dpMin[j+1][i+m] 
              };
              
              for(int k = 0; k < arrMul.length; k++) {
                val = Math.max(val, arrMul[k]);
                valMin = Math.min(valMin, arrMul[k]);
              }
              
              break;
          }
          
          dp[i][i+m] = Math.max(dp[i][i+m], val);
          dpMin[i][i+m] = Math.min(dpMin[i][i+m], valMin);
        }
      }
    }
    
//     for(int i = 0; i < nums.length; i++) {
//       for(int j = 0; j < nums.length; j++) {
//         System.out.print(dp[i][j] + " ");
//       }
//       System.out.println();
//     }
    
    System.out.println(dp[0][length/2]);
  }
}