프로그래머스 문제 - 사칙연산

프로그래머스 [1차] 추석 트래픽 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

숫자와 더하기 빼기 기호 둘 중 한가지가 차례대로 나열된 배열이 있습니다.
빼기를 할 시 연산 순서에 따라 결과가 바뀔 수 있습니다.
주어진 배열의 계산 결과 중 최대값을 구해야합니다.

문제 풀이

일단 dp문제이기 때문에 dfs, bfs를 사용하면 최대 100!만큼 프로그램을 돌리기 때문에 시간초과가 나올 것입니다.
그러니 문제에 알맞는 식을 찾아야합니다.

최대값을 구해야 하기 때문에 2차원 배열을 이용하여 현재 값 = "이전에 구한 값" "연산부호" "이전에 구한 값" 으로 진행하면 답이 나올 수 있을 것입니다.
하지만 -기호가 있는 것을 생각해야 합니다. 그러니
"+"일 경우 최대값 = "이전에 구한 최대값" + "이전에 구한 최대값"
"-"일 경우 최대값 = "이전에 구한 최대값" - "이전에 구한 최소값"
을 해야 최대값을 구할 수 있습니다.
그러면 이전에 구한 값들은 최대값과 최소값 둘 다 저장해두어야 마지막에 최대값을 찾아낼 수 있습니다.

번호들의 수를 알고 있고 k는 연산자가 있는 위치, i는 k위치의 왼쪽, j는 k위치의 오른쪽이라면
연산부호가 "-"일 경우
max_dp = i~k까지 계산한 값의 최대값 - k+1~j까지 계산한 값의 최소값
min_dp = i~k까지 계산한 값의 최소값 - k+1~j까지 계산한 값의 최대값
연산부호가 "+"일 경우
max_dp = i~k까지 계산한 값의 최대값 + k+1~j까지 계산한 값의 최대값
min_dp = i~k까지 계산한 값의 최소값 + k+1~j까지 계산한 값의 최소값
으로 계산이 가능합니다.

전체 코드

#include <bits/stdc++.h>
#include <vector>
#include <string>
using namespace std;

int solution(vector<string> arr)
{
    int answer = -1;
    int max_dp[102][102] = {0,};
    int min_dp[102][102] = {0,};
    int numSize = arr.size()/2+1;
    
    //배열 초기화 및 자기 자신만 계산하는 경우 입력
    for(int i = 0; i < numSize; i++)
    {
        for(int j = 0; j < numSize; j++)
        {
            if(i == j)
            {
                max_dp[i][j] = stoi(arr[i*2]);
                min_dp[i][j] = stoi(arr[i*2]);
            }
            else
            {
                max_dp[i][j] = -10000000;
                min_dp[i][j] = 10000000;
            }
        }
    }
    
    //dp최대값과 최소값을 입력해나가며 계산
    for(int index = 1; index < numSize; index++)
    {
        for(int i = 0; i < numSize - index; i++)
        {
            int j = index + i;
            for(int k = i; k < j; k++)
            {
                if(arr[k * 2 + 1] == "-")
                {
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j]);
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j]);
                }
                else if(arr[k * 2 + 1] == "+")
                {
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j]);
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j]);
                }
            }
        }
    }
    
    answer = max_dp[0][numSize-1];
    return answer;
}

출처

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