[lv.4] 사칙연산

https://school.programmers.co.kr/learn/courses/30/lessons/1843

• 문제
  
  

• 풀이
  (nukeC님의 풀이를 전제로 한다.)
  일단, 식을 보면은 결국엔 (최종식1)+or-(최종식2) 형태일 것이다.
  그렇다는 것은 최종식을 최대로 만들어야한다는 것인데, 사실 뺄셈이란 존재때문에 누가 최소로 와도 사실 최대가 될 것이다.
  그러기에, dp식을 세웠다.
  dp_max[l][r] = l~r 사이의 숫자 연산에서의 최대
dp_min[l][r] = l~r 사이의 숫자 연산에서의 최소
  이후, 덧셈, 뺄셈에서의 최대, 최소 공식을 정리하자면
  덧셈 최대 = dp_max[l][r] + dp_max[r+1][끝];
덧셈 최소 = dp_min[l][r] + dp_min[r+1][끝];
뺄셈 최대 = dp_max[l][r] - dp_min[r+1][끝];
덧셈 최소 = dp_min[l][r] - dp_max[r+1][끝];
  이렇게 정리가 가능하다.
  이때, 슬라이딩 윈도우 기법을 활용하여 l~r의 길이는 고정하되, l+1, r+1을 하고, 다 끝나고 나면 l~r 사이의 길이를 +1한다.
  (연산3+연산1 -> 연산2+연산2...) 이런식이다.
  그렇게 하여 마지막 전체의 최대값인 dp[0][끝]을 리턴한다.

• 후기
  씻팔 lv.4는 이런 맛이구나...
  1시간 30분동안 똥쌀동안 이거 도움 주신 분은 15분만에 푼거 보면 참...

• 코드

import java.util.*;

class Solution {
    public int solution(String arr[]) {
        int[] num = new int[arr.length/2+1];
        int[] op = new int[arr.length/2]; // + : 0, - : 1
        int idx1 = 0;
        int idx2 = 0;
        for(String now : arr){
            if(now.equals("+")) op[idx2++] = 0;
            else if(now.equals("-")) op[idx2++] = 1;
            else num[idx1++] = Integer.parseInt(now);
        }
        int[][] dp_max = new int[arr.length/2+1][arr.length/2+1];
        int[][] dp_min = new int[arr.length/2+1][arr.length/2+1];
        for(int i=0; i<arr.length/2+1; i++){
            dp_max[i][i] = dp_min[i][i] = num[i];
        }
        for(int i=1; i<arr.length/2+1; i++){
            for(int j=0; j<arr.length/2+1; j++){
                if(i+j>=arr.length/2+1) break;
                int e = i+j;
                int max = Integer.MIN_VALUE;
                int min = Integer.MAX_VALUE;
                for(int k=j; k<e; k++){
                    if(op[k]==0){ //덧셈
                        max = Math.max(max, dp_max[j][k] + dp_max[k+1][e]);
                        min = Math.min(min, dp_min[j][k] + dp_min[k+1][e]);
                    }
                    else{
                        max = Math.max(max, dp_max[j][k]-dp_min[k+1][e]);
                        min = Math.min(min, dp_min[j][k]-dp_max[k+1][e]);
                    }
                }
                dp_min[j][e] = min;
                dp_max[j][e] = max;
            }
        }
        return dp_max[0][arr.length/2];
    }
}