[99클럽 코테 스터디 12일차 TIL] 동적계획법

📖 오늘의 학습 키워드
동적계획법

오늘의 회고

문제

[사칙연산]
https://school.programmers.co.kr/learn/courses/30/lessons/1843

나의 해결

import java.util.*;
class Solution {
    public int solution(String arr[]) {
        char[] op = new char[arr.length/2];
        int[][][] dp = new int[arr.length/2+1][arr.length/2+1][2]; 
        int idx1 = 0;
        int idx2 = 0;
        for(String s : arr) {
            if(s.equals("+")) {
                op[idx2++] = '+';
            }
            else if(s.equals("-")) {
                op[idx2++] = '-';
            }
            else {
                int n = Integer.parseInt(s);
                dp[idx1][idx1][0] = n;
                dp[idx1][idx1][1] = n;
                idx1++;
            }
        }
        for(int len = 1; len < arr.length/2+1; len++) {
            for(int start = 0; start < arr.length/2+1; start++) {
                if(start + len >= arr.length/2+1) {
                    break;
                }
                int end = start + len;
                int max = Integer.MIN_VALUE;
                int min = Integer.MAX_VALUE;
                for (int i = start; i < end; i++) {
                    if (op[i] == '+') {
                        max = Math.max(max, dp[start][i][1] + dp[i+1][end][1]);
                        min = Math.min(min, dp[start][i][0] + dp[i+1][end][0]);
                    } 
                    else {
                        max = Math.max(max, dp[start][i][1] - dp[i+1][end][0]);
                        min = Math.min(min, dp[start][i][0] - dp[i+1][end][1]);
                    }
                }
                dp[start][end][0] = min;
                dp[start][end][1] = max;
            }
        }
        return dp[0][arr.length/2][1];
    }
}

1. 배열 op에 arr에 있는 연산자를 순서대로 저장한다.

2. 배열 num에는 arr에 나오는 숫자를 순서대로 저장한다.

3. 범위 내 피연산자들의 연산 최대값과 최소값을 저장하는 dp 배열을 선언한다.

   • dp[i][j][0] : i번째 피연산자부터 j번째 피연산자까지 최소값
     dp[i][j][1] : i번째 피연산자부터 j번째 피연산자까지 최대값

4. 최대값과 최소값을 구하는 방식은 연산자의 종류에 따라 달라진다.

   • +

     • 최대값 : 최대값 + 최대값
       dp[start][i][1] + dp[i+1][end][1]
     • 최소값 : 최소값 + 최소값
       dp[start][i][0] + dp[i+1][end][0]

   • -

     • 최대값 : 최대값 - 최소값
       dp[start][i][1] - dp[i+1][end][0]
     • 최소값 : 최소값 - 최대값
       dp[start][i][0] - dp[i+1][end][1]

5. 처음부터 마지막 피연산자까지의 최대값인 dp[0][arr.length/2][1]를 정답으로 반환한다.

새로 학습한 내용