99클럽 코테 스터디 20일차 TIL - DP (프로그래머스 '사칙연산')

항해99 코테 스터디 20일차 문제인 프로그래머스의 '사칙연산'은 덧셈과 뺄셈만으로 주어진 식에 괄호를 추가하여 구할 수 있는 최댓값을 반환하는 문제다. 난이도는 레벨4이며 DP를 통해 해결할 수 있다.

 

오늘의 문제 - 사칙연산 문제 정보

문제 키워드

- Dynamic Programming

난이도

- Level 4

 

문제 요약

• 숫자와 연산자(+ 또는 -)가 번갈아 들어있는 리스트가 주어졌을 때, 괄호를 원하는 대로 추가하여 나올 수 있는 결과 중 최대값을 구하시오.

 

문제 풀이 과정  

• 계속 헤매다가 도저히 떠오르지 않아서 좋은 해설글을 참고했다.
• 가장 중요한 포인트는, 뺄셈 연산의 최댓값을 구하기 위해 최솟값도 가지고 있어야 한다는 부분이다.
• 이를 이용해 모든 구간의 최댓값과 최솟값을 구해가면서 최종적으로 전체 식의 최댓값을 반환하면 되는 문제였다.

↓↓↓ 참고한 좋은 해설 ↓↓↓

프로그래머스

 

 

코드

class Solution {
    public int solution(String arr[]) {
        int N = (arr.length + 1) / 2;
        // DP[i][j]: i부터 j번째 '숫자'까지 계산했을 때의 최솟값/최댓값
        int[][] minDP = new int[N][N]; // 빼기 연산에서 최댓값을 알기 위해 최솟값도 알고 있어야 함
        int[][] maxDP = new int[N][N];
        
        // 최댓값 배열과 최솟값 배열을 초기화
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                minDP[i][j] = Integer.MAX_VALUE;
                maxDP[i][j] = Integer.MIN_VALUE;
            }
        }
        
        // step: i와 j의 간격. 매 step마다 step 간격의 DP[i][j] 모두 계산
        // ex) step=2 -> DP[0][2], DP[1][3], DP[2][4], ...
        for (int step=0; step<N; step++) {
            for(int i=0; i<N-step; i++) {
                // 간격이 0인 경우는 자기 자신이 최댓값이자 최솟값임
                if (step == 0) {
                    minDP[i][i] = Integer.valueOf(arr[2*i]);
                    maxDP[i][i] = Integer.valueOf(arr[2*i]);
                    continue;
                }
                
                // i번째 숫자부터 j번째 숫자 내에서, 
                // DP[i][k]와 DP[k+1][j]를 부호에 따라 더하거나 빼서 최댓값/최솟값을 갱신
                // ex) DP[1][4]를 구하기 위해 DP[1][1]&DP[2][4], DP[1][2]&DP[3][4], DP[1][3]&DP[4][4]를 사용
                int j = i + step;
                for(int k=i; k<j; k++) {
                    if (arr[2*k+1].equals("+")) {
                        maxDP[i][j] = Integer.max(maxDP[i][j], maxDP[i][k] + maxDP[k+1][j]);
                        minDP[i][j] = Integer.min(minDP[i][j], minDP[i][k] + minDP[k+1][j]);
                    } else {
                        maxDP[i][j] = Integer.max(maxDP[i][j], maxDP[i][k] - minDP[k+1][j]);
                        minDP[i][j] = Integer.min(minDP[i][j], minDP[i][k] - maxDP[k+1][j]);
                    }
                }
            }
        }
        
        return maxDP[0][N-1];
    }
}

 

오늘의 학습 회고

새롭게 알게된 것

• DP는 역시 어렵다!