[Java] 찾아라 프로그래밍 마에스터 (사칙 연산)

문제 설명

---

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.

• ((1 - 5) - 3) = -7
• (1 - (5 - 3)) = -1

위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다.
또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.

• (((1 - 3) + 5) - 8) = -5
• ((1 - (3 + 5)) - 8) = -15
• (1 - ((3 + 5) - 8)) = 1
• (1 - (3 + (5 - 8))) = 1
• ((1 - 3) + (5 - 8)) = -5

위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다.
문자열 형태의 숫자와, 더하기 기호("+"), 뺄셈 기호("-")가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• arr는 두 연산자 "+", "-" 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
  • arr의 길이는 항상 홀수입니다.
  • arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
  • 숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : "456")
• 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

---

입출력 예

arrresult

["1", "-", "3", "+", "5", "-", "8"]	1
["5", "-", "3", "+", "1", "+", "2", "-", "4"]	3

입출력 예시

입출력 예 #1
위의 예시와 같이 (1-(3+(5-8))) = 1 입니다.

입출력 예 #2
(5-(3+((1+2)-4))) = 3 입니다.

 

 

접근 방법

---

개인적으로 굉장히 재미있게 풀었던 문제입니다. 

문제를 해결하기 위해서는 부분문제를 해결하며 전체의 최적해를 찾아가는 동적 계획법을 사용할 수 있습니다.

 

1. [A1 ~ An] + [B1 ~ Bn] 의 최대값을 구하기 위해서는 [A1 ~ An]이 최대가 되어야하고 [B1 ~ Bn]이 최대가 되어야 할 것입니다. 

2. [A1 ~ An] - [B1 ~ Bn] 의 최대값을 구하기 위해서는 [A1 ~ An]이 최대가 되어야하고 [B1 ~ Bn]이 최소가 되어야 할 것입니다. 

3. [A1 ~ An] = [A1 ~ Ax] + [Ax+1 ~ An]또는 [A1 ~ Ax] - [Ax+1 ~ An] 표현할 수 있습니다. 즉 부분 문제부터 해결하며 최적해를 구합니다. 이 때 중복되는 연산을 없애기 위해 dp테이블을 구성합니다.

 

4. dp테이블은 3차원으로 구성할 수 있습니다.

dp[최대 or 최소][범위의 시작][범위의 끝] = 범위의 최대 혹은 최소 값

dp테이블의 1차원은 0또는 1로써 최대값을 저장하는 테이블인지 최소값을 저장하는 테이블인지 지정하며 그에 따른 값을 dp테이블에 기록합니다.

 

ex1) dp[0][3][7] -> 3번째 숫자부터 7번째 숫자까지의 최대값

ex2) dp[1][2][7] -> 2번째 숫자부터 7번째 숫자까지의 최소값

 

자세한 내용은 아래 소스코드에 주석처리 하였습니다.

 

소스 코드

---

class Solution {
    
    //dp의 1차원의 0은 최대 테이블, 1은 최소테이블
    int dp[][][] = new int[2][200][200]; 
    char oper[]; int nums[]; //oper는 연산자를 기록, nums는 숫자를 기록
    String arr[];
    int tmp = 987654321;
    
    //dp테이블 초기화
    public void init(){
        
        int n = arr.length/2;
        
        for(int i=0;i<n+1;i++)
            for(int j=0;j<n+1;j++){
                dp[0][i][j] = -1 * tmp;
                dp[1][i][j] = tmp;            
            }
            
        nums = new int[n + 1];
        oper = new char[n];
        
        //arr의 짝수 idx는 숫자가 기록, 홀수 idx에는 연산자가 기록되어 있음
        for(int i=0;i<arr.length;i++){
            if(i%2 == 0) nums[i/2] = Integer.parseInt(arr[i]);
            else oper[i/2] = arr[i].charAt(0);
        }
    }
    
    //flag == 0이면 최대, 1이면 최소
    public int solve(int flag, int start, int end){
        
        // 범위가 숫자 하나로 일치하는 경우
        if(start == end)
            return dp[flag][start][end] = nums[start];
        
        //이미 해결했던 문제라면
        if(flag == 0 && dp[flag][start][end] != -1*tmp)
            return dp[flag][start][end];
        if(flag == 1 && dp[flag][start][end] != tmp)
            return dp[flag][start][end];
        
        // flag에 따라 초기값을 다르게 줌
        int ret = (flag == 0) ? -1 * tmp : tmp;
        // 방문 체크
        dp[flag][start][end] = 0;
        
        if(flag == 0){
        //최대를 구해야 하는 경우
            for(int mid = start; mid < end; mid++){
                if(oper[mid] == '-') //두 구간 사이의 연산자가 "-"일때, 최대 - 최소
                    ret = Math.max(ret, solve(0, start, mid) - solve(1, mid+1, end));        
                else //두 구간 사이의 연산자가 "+"일때, 최대 + 최대
                    ret = Math.max(ret, solve(0, start, mid) + solve(0, mid+1, end));
            }    
        }
        else{
        //최소를 구해야 하는 경우
            for(int mid = start; mid < end; mid++){
                if(oper[mid] == '-') //두 구간 사이의 연산자가 "-"일때, 최소 - 최대
                    ret = Math.min(ret, solve(1, start, mid) - solve(0, mid+1, end));        
                else //두 구간 사이의 연산자가 "+"일때, 최소 + 최소
                    ret = Math.min(ret, solve(1, start, mid) + solve(1, mid+1, end));
            }
        }
        return dp[flag][start][end] = ret;
    }
    
    public int solution(String arr[]) {
        int answer = -1;
        this.arr = arr;
        init();
        // solve(처음부터 마지막의 최대값), flag = 0, start = 0, end = 마지막 idx
        return answer = solve(0, 0, arr.length/2);
    }
}