99클럽 코테 스터디 20일차 TIL: [프로그래머스] 사칙연산

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

프로그래머스

 

주어진 식에 대한 연산의 최댓값을 구하는 문제이다. 예를 들어 1 - 3 + 5 - 8라는 식이 주어졌을 때 괄호의 위치에 따라 여러 연산 결과가 나오는데 그 중 최댓값을 구하면 된다.

• 이때 다음과 같은 dp 개념이 사용된다.
  • A + B의 최댓값을 구하려면, A와 B 둘 다 최댓값이어야 한다.
  • A - B의 최댓값을 구하려면, A는 최댓값, B는 최솟값이어야 한다.
• 위와 같이 - 연산자의 뒤에 있는 수는 최솟값이 되어야 전체 연산 결과가 최댓값이 될 수 있다. 따라서 연산의 최댓값을 dp로 저장해둬야 하며, 그 뿐만 아니라 최솟값도 저장해둬야 한다. 따라서 3차원 배열이 필요하다.
  • dp[0][i][j] = 인덱스 i부터 j까지의 값들을 연산했을 때 최댓값
  • dp[1][i][j] = 인덱스 i부터 j까지의 값들을 연산했을 때 최솟값
• 그리고 i부터 j까지의 값들을 연산했을 때의 최댓값과 최솟값을 구하기 위해선, 중간 인덱스를 두고 각 경우를 모두 살핀 후 모든 경우 중 최댓값과 최솟값을 골라내야 한다.
  • i = 0, j = 5일 때
    • 인덱스 0 ~ 0까지의 최댓값 + 인덱스 1 ~ 5까지의 최댓값 (중간 인덱스 = 0)
    • 인덱스 0 ~ 1까지의 최댓값 + 인덱스 2 ~ 5까지의 최댓값 (중간 인덱스 = 1)
    • 인덱스 0 ~ 2까지의 최댓값 + 인덱스 3 ~ 5까지의 최댓값 (중간 인덱스 = 2)
    • 인덱스 0 ~ 3까지의 최댓값 + 인덱스 4 ~ 5까지의 최댓값 (중간 인덱스 = 3)
    • 인덱스 0 ~ 4까지의 최댓값 + 인덱스 5 ~ 5까지의 최댓값 (중간 인덱스 = 4)

class Solution {
    
    int n;
    int[] nums;
    char[] opers;
    int[][][] dp;
    
    public int solution(String arr[]) {
        
        n = arr.length / 2;
        nums = new int[n + 1];
        opers = new char[n];
        dp = new int[2][n + 1][n + 1];
        
        // dp 배열 초기화
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                dp[0][i][j] = Integer.MIN_VALUE;
                dp[1][i][j] = Integer.MAX_VALUE;
            }
        }
        
        // nums, opers 배열 초기화
        for (int i = 0; i < arr.length; i++) {
            if (i % 2 == 0) {
                nums[i / 2] = Integer.parseInt(arr[i]); 
            } else {
                opers[i / 2] = arr[i].charAt(0);
            }
        }
        
        return solve(0, 0, n); // nums의 인덱스 0 ~ n까지의 연산의 최댓값
    }
    
    // flag: 0(최댓값), 1(최솟값)
    public int solve(int flag, int start, int end) {
        if (start == end) {
            dp[flag][start][end] = nums[start];
        }
        
        // 이미 결과를 계산한 경우
        if (flag == 0 && dp[flag][start][end] != Integer.MIN_VALUE) {
            return dp[flag][start][end];
        }
        if (flag == 1 && dp[flag][start][end] != Integer.MAX_VALUE) {
            return dp[flag][start][end];
        }
        
        // start ~ end까지의 연산 계산
        int result = (flag == 0) ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        if (flag == 0) { // 최댓값 계산
            for (int mid = start; mid < end; mid ++) {
                if (opers[mid] == '-') { // 최댓값 = 최대 - 최소
                    result = Math.max(result, solve(0, start, mid) - solve(1, mid + 1, end));
                } 
                if (opers[mid] == '+') { // 최댓값 = 최대 + 최대
                    result = Math.max(result, solve(0, start, mid) + solve(0, mid + 1, end));
                } 
            }
        }
        if (flag == 1) { // 최솟값 계산
            for (int mid = start; mid < end; mid ++) {
                if (opers[mid] == '-') { // 최솟값 = 최소 - 최대
                    result = Math.min(result, solve(1, start, mid) - solve(0, mid + 1, end));
                } 
                if (opers[mid] == '+') { // 최솟값 = 최소 + 최소
                    result = Math.min(result, solve(1, start, mid) + solve(1, mid + 1, end));
                } 
            }
        }
        
        // dp에 메모이제이션
        dp[flag][start][end] = result;
        return result;
    }
}