[프로그래머스][level4] 사칙연산 (C++)

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

코딩테스트 연습 - 사칙연산

 

 

[난이도] level4
[유형] DP

[풀이]
연산자의 수가 최대 N=100개가 될 수 있으므로 이것을 순열로 만들어 모든 연산 순서에
대해 해보는 풀이로는 해결할 수 없습니다.

다이나믹 프로그래밍을 이용하면 O(N^2)의 복잡도로 해결이 가능합니다.

재귀를 이용한 Top-Down DP를 이용하였으며

sol(int l,int r,int k) 함수는 dp[l][r][k]를 구하며 리턴합니다.

정의는 아래와 같습니다.
dp[l][r][k] : if k==0
                l~r번째 연산자 구간의 연산결과의 최솟값
              if k==1
                l~r번째 연산자 구간의 연산결과의 최댓값

배열의 길이가 2n+1 이라면 연산자는 총 n개 존재하며 각 연산자는 0~n-1 index를 갖는다고 가정합니다.

만약 아래와 같은 배열이 있다면 "-","-","+"연산자는 각각 index 0,1,2 입니다.
["1","-","5","-","3","+","8"]

l~r번째 연산자 구간의 의미는 전체 배열 arr에서는 arr[2*l] , arr[2*l+1] ... arr[2*r+2] 를 모두 사용했을 때,
즉 2*l~2*r+2 구간의 모든 숫자와 연산자를 사용했을 때의 최소 혹은 최댓값을 의미합니다.

예를들어, ["1","-","5","-","3","+","8"] 에서 1~2번째 연산자 구간의 값을 구하는 것은
("5","-","3","+","8")를 모두 사용한 값을 구하는 것이므로 arr[2*1] ~ arr[2*2+2] 를 모두 사용하는 것을 의미합니다.

dp[l][r][k] 를 구하려면

l~r 구간을 어떤 연산자를 기준으로 나눌지를 정해야 합니다.
만약 l이상 r이하의 i로 구간을 나눈다면

k가 0,1인 경우, arr[2*i+1]가 "+","-"인 경우가 나눠지므로 총 4가지 케이스의 식이 나옵니다.

a) k==0
    a-1) arr[i]=="+"
        sol(l,r,k) = sol(l,i-1,0) + sol(i+1,r,0)
        위와 같이 구할 수 있습니다. l~i-1 연산자 구간, i+1~r 연산자 구간의 최댓값 구하면 됩니다.
        만약 l>i-1 인 경우 좌측에 더이상 연산자가 없다는 의미이므로 arr[2*l] 값을 그대로 사용하면 되고,
        i+1>r 인 경우도 역시 우측에 더이상 연산자가 없다는 의미이므로 arr[2*r+2] 값을 그대로 사용하면 됩니다.
        이는 다른 케이스에서도 동일하게 적용됩니다.

        arr[i]=="+" 이므로 더하기 연산을 해야하는데 k==0으로, 최솟값을 구해야 하므로
        l~i-1 구간의 최솟값, i+1~r 구간의 최솟값을 더하는 것이 최솟값을 구할 때 가장 최적이므로
        sol(l,i-1,0) + sol(i+1,r,0) 와 같이 최솟값을 구하기 위해 3번째 인자로 0을 넣어주었습니다.

    a-2) arr[i]=="-"
        sol(l,r,k) = sol(l,i-1,0) + sol(i+1,r,1)

        첫번째 케이스와 마찬가지로 lvalue - rvalue 형태가 나와야 하는데 최솟값이 되려면
        lvalue는 최소, rvalue는 최대가 되는 것이 최적입니다.
        그러므로 위와 같은 식이 나옵니다.

    모든 i에 대해 위와 같이 식을 구해본 뒤 나온 값을 중에 "최솟"값이 sol(l,r,k) 의 최종 결과가 됩니다.

b) k==1
    b-1) arr[i]=="+"
        sol(l,r,k) = sol(l,i-1,1) + sol(i+1,r,1)
        lvalue + rvalue형태이므로 lvalue는 최대, rvalue는 최대인 것이 최댓값을 만들 때 최적입니다.

    b-2) arr[i]=="-"
        sol(l,r,k) = sol(l,i-1,1) + sol(i+1,r,0)
        lvalue + rvalue형태이므로 lvalue는 최대, rvalue는 최소인 것이 최댓값을 만들 때 최적입니다.

    모든 i에 대해 위와 같이 식을 구해본 뒤 나온 값을 중에 "최댓"값이 sol(l,r,k) 의 최종 결과가 됩니다.

 

 

#include <vector>
#include <string>
#include <cstring>
using namespace std;
int dp[101][101][2],inf=9e8;
vector<string> arr;
int sol(int l,int r,int k){
    int& ret = dp[l][r][k];
    if(ret!=-1) return ret;
    if(k){
        ret=-inf;
        for(int i=l;i<=r;i++){
            int lv,rv;
            lv = l>i-1 ? stoi(arr[2*l]) : sol(l,i-1,1);
            if(i+1>r) rv = stoi(arr[2*r+2]);
            else if(arr[2*i+1]=="+") rv = sol(i+1,r,1);
            else rv = sol(i+1,r,0);

            if(arr[2*i+1]=="+") ret=max(lv+rv,ret);
            else ret=max(lv-rv,ret);
        }
    }else{
        ret=inf;
        for(int i=l;i<=r;i++){
            int lv,rv;
            lv = l>i-1 ? stoi(arr[2*l]) : sol(l,i-1,0);
            if(i+1>r) rv = stoi(arr[2*r+2]);
            else if(arr[2*i+1]=="+") rv = sol(i+1,r,0);
            else rv = sol(i+1,r,1);

            if(arr[2*i+1]=="+") ret=min(lv+rv,ret);
            else ret=min(lv-rv,ret);
        }        
    }
    return ret;
}

int solution(vector<string> _arr)
{
    memset(dp,-1,sizeof(dp));
    arr=_arr;
    return sol(0,arr.size()/2-1,1);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/사칙연산.cpp