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

문제

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

프로그래머스

접근방법

dp문제인 걸 알고 풀어도,

어떤 데이터를 dp 테이블에 저장해야할 지 모르면 말짱 꽝이다.

 

처음엔 지난 번에 했던 방법대로

possible_set을 만들어서 해결하면 될 것 같다는 생각을 했지만, 

먹히지 않았다.

 

해결법은 다음과 같았다.

1. 2차원 dp테이블 2개 이용한다(mindp, maxdp).

2. 괄호의 개수를 늘려가면서 2차원 dp테이블에 값을 저장한다.

3. dptable에 저장된 maxdp[0][n/2]의 값을 리턴한다.

 

2차원 dp테이블 2개(mindp, maxdp)를 사용하는 이유는 다음과 같다.

1) 연산자가 -인 경우, 최대값을 구하기 위해서 (max) - (min)이 되어야한다.

2) 연산자가 +인 경우, 최대값을 구하기 위해서는 (max) + (max)가 되어야한다.

따라서, 각 괄호마다 max와 min값을 각각 저장해 두는 것이다.

 

코드

#include <vector>
#include <string>
#include <iostream>

using namespace std;

int solution(vector<string> arr)
{
    int answer = -1;
    int n = arr.size();
    vector<vector<int> > maxdp(n/2 + 1, vector<int>(n/2 + 1, -10000000));
    vector<vector<int> > mindp(n/2 + 1, vector<int>(n/2 + 1, 10000000));

    for (int i=0, j=0;i<n;i += 2,j++) {
        maxdp[j][j] = stoi(arr[i]);
        mindp[j][j] = stoi(arr[i]);
    }
    for (int d=1;d<n/2 + 1;d++) {
        for (int l=0;l<n/2 + 1 - d;l++) {
            int r = d + l;
            for (int pos=l;pos < r;pos++) {
                if (arr[2 * pos + 1] == "+") {
                    maxdp[l][r] = max(maxdp[l][r], maxdp[l][pos] + maxdp[pos+1][r]);   
                    mindp[l][r] = min(mindp[l][r], mindp[l][pos] + mindp[pos+1][r]);
                } else {
                    maxdp[l][r] = max(maxdp[l][r], maxdp[l][pos] - mindp[pos+1][r]);
                    mindp[l][r] = min(mindp[l][r], mindp[l][pos] - maxdp[pos+1][r]);   
                }
            }
        }
    }
    answer = maxdp[0][n/2];
    return answer;
}

개선할 점

..