[Algorithm] 프로그래머스 - 사칙연산

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

접근

주어진 배열 arr 에서 괄호를 묶을 수 있는 모든 조합 중에 계산 결과가 최대가 되는 경우를 찾아야 하는 문제다.

arr 의 길이가 $3\leq{...}\leq{201}$ 이므로 완전 탐색은 할 수 없다.

연산의 중요한 특징은 연산의 결과를 재사용해서 다른 결과를 만들 수 있다는 것이다.

즉, 다이나믹 프로그래밍(Dynamic Programming)의 요건 중 Optimal Substructure를 만족한다.

문제의 정답을 작은 문제에서 구할 수 있기 때문이다.

그렇다면 이 문제를 작은 문제로 쪼갤 수 있는지(Overlapping Subproblem)를 검증하는 과정을 거쳐야 한다.

$1-3+5-8$ 의 경우 두 숫자에 대해 파생되는 괄호쌍은

$(1-3)+5-8$ , $1-(3+5)-8$ , $1-3+(5-8)$ 이다.

괄호쌍을 찾는 과정에서 계산 결과가 같은 경우가 많은데,

이 과정은 이 문제를 DP로 바라볼 수 있는지 검증하는 과정이기 때문에 그 문제는 중요한 게 아니다.

이어서 알아보자. 세 숫자에 대해 파생되는 괄호쌍은

$(1-3+5)-8$ , $1-(3+5-8)$ 이다.

하지만, 이렇게 간단히 숫자 개수의 범위를 늘려간다고 해서 이 문제를 DP로 볼 수 없다.

파생된 괄호쌍을 하나의 연산 결과로 보고 새로운 괄호쌍의 조합이 파생될 수 있기 때문이다.

즉, 두 숫자에 대해 파생되는 괄호쌍에 대해 다시 새로운 괄호쌍의 조합이 파생될 수 있다.

$((1-3)+5)-8$ , $(1-(3+5))-8$ , $1-((3+5)-8)$ , $1-(3+(5-8))$ 이 그런 경우의 괄호쌍이다.

결과적으로 나올 수 있는 조합이 예상보다 더 많아졌으므로 복잡해졌다고 할 수 있지만,

이 문제를 DP로 바라보면 문제는 더 간단해진다.

작은 범위부터 시작해 각 괄호쌍 조합을 담는 배열을 정의하고 각 조합마다 최대가 되는 결과를 저장하면 된다.

그러면 큰 범위에서도 작은 범위에서 구한 결과로 문제를 해결할 수 있다.

하지만, 여기서 끝이 아니고 생각할 것이 하나 더 있다. 바로 - 의 존재인데,

이는 단순히 최대가 되는 결과만을 저장한다고 해서 Overlapping Subproblem을 만족한다고 볼 수 없다.

$Oprnd1 - Oprnd2$ 과 같이 - 연산에 대해 두 피연산자로 구분된 경우를 생각해봐야 한다.

이 연산의 결과가 최대가 되려면 $Oprnd1$ 가 최대가 돼야 함은 변함이 없지만,

$Oprnd2$ 는 최소가 돼야 최종적으로 최대가 되는 결과를 구할 수 있다.

따라서 DP 중에 각 괄호쌍 조합마다 최대가 되는 경우와 최소가 되는 경우 모두 저장해 문제를 해결해야 한다.

소스코드(Java) - 1

class Solution {
    public int solution(String arr[]) {

        int[][][] dp = new int[arr.length][arr.length][2];
        int[] num = new int[arr.length];

        for(int i = 0; i < arr.length; i+=1) {
            if(arr[i].equals("+")) num[i] = 0;
            else if(arr[i].equals("-")) num[i] = -1;
            else {
                dp[i][i][0] = dp[i][i][1] = num[i] = Integer.parseInt(arr[i]);
            }
        }

        for(int len = 2; len < arr.length; len+=2) {
            for(int s = 0; s < arr.length; s+=2) {
                if(s + len >= arr.length) break;
                int e = s + len;
                int min = Integer.MAX_VALUE;
                int max = Integer.MIN_VALUE;

                for(int i = s; i < e; i+=2) {
                    if(num[i+1] == 0) {
                        max = Math.max(max, dp[s][i][0]+dp[i+2][e][0]);
                        min = Math.min(min, dp[s][i][1]+dp[i+2][e][1]);
                    } else if(num[i+1] == -1) {
                        max = Math.max(max, dp[s][i][0]-dp[i+2][e][1]);
                        min = Math.min(min, dp[s][i][1]-dp[i+2][e][0]);
                    }
                }

                dp[s][e][0] = max;
                dp[s][e][1] = min;
            }
        }

        return dp[0][arr.length-1][0];
    }
}

 

앞서 숫자 개수의 범위를 점점 늘려 가며 최종적으로 문제를 해결한다.

Overlapping Subproblem를 만족하는 경우가 고정되어 있으므로 Optimal Substructure를 만족하는 범위에서 iteration을 조정해서 조금 다르게 문제에 접근할 수도 있다.

소스코드(Java) - 2

class Solution {
    public int solution(String arr[]) {

        int[][][] dp = new int[arr.length][arr.length][2];
        int[] num = new int[arr.length];

        for(int i = 0; i < arr.length; i+=1) {
            if(arr[i].equals("+")) num[i] = 0;
            else if(arr[i].equals("-")) num[i] = -1;
            else {
                dp[i][i][0] = dp[i][i][1] = num[i] = Integer.parseInt(arr[i]);
            }
        }

        for(int s = arr.length - 3; s >= 0; s-=2) {
            for(int e = s+2; e < arr.length; e+=2) {
                int min = Integer.MAX_VALUE;
                int max = Integer.MIN_VALUE;

                for(int i = e-2; i >= s; i-=2) {
                    if(num[i+1] == 0) {
                        max = Math.max(max, dp[s][i][0]+dp[i+2][e][0]);
                        min = Math.min(min, dp[s][i][1]+dp[i+2][e][1]);
                    } else if(num[i+1] == -1) {
                        max = Math.max(max, dp[s][i][0]-dp[i+2][e][1]);
                        min = Math.min(min, dp[s][i][1]-dp[i+2][e][0]);
                    }
                }

                dp[s][e][0] = max;
                dp[s][e][1] = min;
            }
        }

        return dp[0][arr.length-1][0];
    }
}

 

여기서는 일정 길이를 뜻하는 len 을 사용하지 않고 범위 시작 인덱스 s 를 끝에서 점점 감소시키고, 범위 끝 인덱스 e 를 s 에서 점점 증가시키며 Optimal Substructure를 만족하고 있다.

계속해서 작은 문제의 결과가 큰 문제에서 Overlapping Subproblem을 만족하면서 재사용되기 때문이다.

그렇다고 해서 아무렇게나 iteration을 하면 두 요건을 모두 만족할 수 없으므로 반드시 두 요건을 고려해야 한다.