[백준 16637]괄호 추가하기

괄호 추가하기

A. 접근법

연산자 우선순위가 동일하기 때문에 왼쪽부터 계산한다는 조건, 괄호 안에는 연산자가 하나만 있어야 한다는 조건으로 인해서 문제 접근은 DP로 접근해야겠다는 생각이 들었다.(시간 제한도 0.5초로 짧다)

dp[N]: N개의 숫자가 주어졌을 때 괄호를 추가해서 얻을 수 있는 최대값을 저장하는 배열.
mdp[N]: N개의 숫자가 주어졌을 때 괄호를 추가해서 얻을 수 있는 최소값을 저장하는 배열.

dp[N]는 아래 셋 중에 최대값을 저장해야한다.

1. dp[N - 1]과 N번째 숫자를 계산
2. dp[N - 2]와 (N, N - 1번째 숫자를 계산한 값)을 계산.
3. mdp[N - 2]와 (N, N - 1번째 숫자를 계산한 값)을 계산. -> mdp[N - 2]가 음수인데 (N, N - 1)을 계산한 것이 음수여서 둘이 곱하여서 최대값이 될 수있다.

처음에는 3번 조건을 고려하지 않아 틀려서 문제의 질문 검색을 통해서 알게되었다.

B. 구현

C. 코드

#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;
#define ll long long
char fm[19];

// 최대값을 저장하는 배열.
vector<ll> dp;
// 최소값을 저장하는 배열.
vector<ll> mdp;

int T, N;

// 문자로 된 값과 연산자를 통해 계산하는 함수.
ll cal(ll a, ll b, char c) {
    ll ret = 0;
    switch(c) {
        case '+':
            ret = a + b;
            break;
        case '-':
            ret = a - b;
            break;
        case '*':
            ret = a * b;
            break;
        default:
            //cout << "NO!" << endl;
            break;
    }
    return ret;
}
void solver(int n) {

    if(n == 0) {
        dp.push_back(atoi(&fm[0]));
        mdp.push_back(atoi(&fm[0]));
    }
    else if(n == 1) {
        dp.push_back(cal(atoi(&fm[0]), atoi(&fm[2]), fm[1]));
        mdp.push_back(cal(atoi(&fm[0]), atoi(&fm[2]), fm[1]));
    }
    else {
        ll a = dp[dp.size() - 2];
        ll b = dp[dp.size() - 1];
        ll c = mdp[mdp.size() - 2];
        ll d = mdp[mdp.size() - 1];

        char oa = 2 * (n - 2) + 1;
        char ob = 2 * (n - 1) + 1;

        dp.push_back(max(cal(b, atoi(&fm[2 * n]), fm[ob]), cal(a, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa])));
        dp[dp.size() - 1] = max(dp[dp.size() - 1], cal(c, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa]));

        mdp.push_back(min(cal(d, atoi(&fm[2 * n]), fm[ob]), cal(c, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa])));
        mdp[dp.size() - 1] = min(mdp[mdp.size() - 1], cal(a, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa]));
    }

    if(N / 2 == n)
        return;
    else
        solver(n + 1);
}

int main() {
    //scanf("%d", &T);
    T = 1;
    for(int tc = 0; tc < T; tc++) {
        scanf("%d", &N);

        scanf("%s\n", fm);
        dp.clear();
        mdp.clear();
        solver(0);

        printf("%d\n", dp[dp.size() - 1]);
    }
    return 0;
}

D. 결과