사칙 연산 - 프로그래머스

문제

문제 난이도 : 프로그래머스 4단계

문제 분류 : 다이나믹 프로그래밍

 

문제 리뷰

내가 이게 DP 문제라는 걸 몰랐다면 풀 수 있었을까..?

그리고 처음에는 DP[i][j] 이런 식으로 둬서 덧붙일때 + 만 고려되었다.

테스트 케이스는 맞길래 뭐지 했는데, - 일 경우에는 - (최소값)으로 해야지 최대값으로 갱신할 수 있다.

물론 질문하기에 자세하게 해설해 놓은게 있지만, 기억용으로...

 

문제 소스코드

#include <vector>
#include <string>
#include <iostream>
#include <unordered_set>
using namespace std;

int solution(vector<string> arr)
{
    int answer = -1;
    vector<int> IntArr;
    vector<string> OperArr;
    IntArr.push_back(-1);
    OperArr.push_back(" ");
    int DP[200][200][2];
    int n;
    for(string s : arr){
        if(s == "-" ||s == "+"){
            OperArr.push_back(s);
        }else{
            IntArr.push_back(atoi(s.c_str()));
        }
    }
    n = OperArr.size();
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            DP[i][j][0] = + 99999999;
            DP[i][j][1] = - 99999999;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j){
                DP[i][j][0] =(IntArr[i]);
                DP[i][j][1] =(IntArr[i]);
            }
        }
    }
    for(int i = 1; i <= n - 1; i++){
        if(OperArr[i] == "+"){
            DP[i+1][i][0]=(IntArr[i] + IntArr[i+1]);
            DP[i+1][i][1]=(IntArr[i] + IntArr[i+1]);
        }else{
            DP[i+1][i][0]=(IntArr[i] - IntArr[i+1]);
            DP[i+1][i][1]=(IntArr[i] - IntArr[i+1]);
        }
    }
    
    for(int Len = 2; Len <= n; Len++){
        for(int j = 1; j <= n - Len; j++){
            for(int p = 0; p < Len ; p++){
                if(OperArr[j+p] == "+"){
                    DP[j+Len][j][1] = max(DP[j+Len][j][1], DP[p+j][j][1] + DP[j+Len][j+p+1][1]);
                    DP[j+Len][j][0] = min(DP[j+Len][j][0], DP[p+j][j][0] + DP[j+Len][j+p+1][0]);
                }else{
                    DP[j+Len][j][1] = max(DP[j+Len][j][1], DP[p+j][j][1] - DP[j+Len][j+p+1][0]);
                    DP[j+Len][j][0] = min(DP[j+Len][j][0], DP[p+j][j][0] - DP[j+Len][j+p+1][1]);
                }
            }
        }
    }
    /*
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            cout << DP[i][j] << " ";
        }
        cout << endl;
    }
    */
    answer = DP[n][1][1];
    
    return answer;
}