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

  이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 이 문제는 다이나믹 프로그래밍을 이용한 행렬 계산 수 줄이기에서 사용하는 테크닉과 매우 유사하게 풀 수 있다. 일단 입력 배열에서 짝수번 인덱스는 숫자를, 홀수번 인덱스는 연산자를 나타내는 것을 확인할 수 있고, 전역 배열을 두개를 놓아 따로 배치했다. 여기서 중요한 것은 예를 들어 0번째 숫자, 1번째 숫자에 대한 연산자는 0번 인덱스이고, 2번째 숫자, 3번째 숫자에 대한 연산자는 2번 인덱스라는 것이다.

 

 

 가장 중요한 점화식을 나는 다음과 같이 간략하게 생각했다.

 f(s, e) : max { f(s, k) + f(k + 1, e) (0 <= k <= e - 1) }

 

 탑다운 방식으로 재귀를 이용하는게 구현이 훨씬 쉬웠다. 여기서 또 중요한 점은 prev의 존재인데, 처음에는 이게 없이 단순하게 max를 찾는 방식으로 했다가 오답이 나왔다.

 

 f + g 의 경우 f와 g 모두 가장 큰 값이 나와야 하고, f - g 의 경우 f는 가장 큰 값, g는 가장 작은 값이 나와야 한다. 하지만 g 내부에서도 f' + g' , f' - g' 과 같은 형태가 나올 것이고, 전자의 경우는 f'은 작은 값, g' 도 작은값 / 후자의 경우는 f'은 작은 값, g' 은 큰값이 나와야 g가 가장 작은 값이 나올 수 있다. 따라서 네 가지 경우가 존재하고, 해당 함수가 큰 값을 리턴해야하는지 작은 값을 리턴해야하는지에 대해 prev 로 설정해주었다.

 

 

여기까지 하면 dp를 적용하는 것은 어렵지 않다. 단순히 3차원 배열을 선언하고, 값이 있으면 리턴, 없으면 값 구하고 저장 후 리턴하면 끝이다.

 

 

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

using namespace std;

#define MIN -10000000
#define MAXNUM 101
#define MAX 10000000

int dp[MAXNUM][MAXNUM][2];

vector<int> number;
vector<char> oper;

// prev 0 : 작아야함 prev 1 : 커야함
int func(int start, int end, int prev) {
    if (start == end) {
        return number[start];
    }
    
    if (dp[start][end][prev] != MIN) {
        return dp[start][end][prev];
    }
    
    int result;
    if (prev == 1) {
        result = MIN;
    }
    else {
        result = MAX;
    }
    
    for (int k = start; k <= end - 1; k++) {
        int temp;
        if (oper[k] == '+') {
            if (prev == 1) {
                temp = func(start, k, 1) + func(k + 1, end, 1);
            }
            else {
                temp = func(start, k, 0) + func(k + 1, end, 0);   
            }
        }
        else {
            if (prev == 1) {
                temp = func(start, k, 1) - func(k + 1, end, 0);    
            }
            else {
                temp = func(start, k, 0) - func(k + 1, end, 1);
            }
        }
        
        if (prev == 1) {
            result = max(result, temp);
        }
        else {
            result = min(result, temp);
        }
    }
    
    return dp[start][end][prev] = result;
}

int solution(vector<string> arr) {
    int answer = -1;
    
    for (int i = 0; i < arr.size(); i++) {
        if (i % 2 == 0) {
            number.push_back(stoi(arr[i]));
        }
        else {
            oper.push_back(arr[i][0]);
        }
    }
    
    for (int y = 0; y < MAXNUM; y++) {
        for (int x = 0; x < MAXNUM; x++) {
            for (int i = 0; i < 2; i++) {
                dp[y][x][i] = MIN;
            }
        }
    }
    
    answer = func(0, number.size() - 1, 1);

    return answer;
}