백준 16637번 괄호 추가하기 - C++(cpp) 풀이 + 그림 설명

---

 

1. 앞에서부터 차례로 괄호를 하는 경우와 안 하는 경우를 모두 고려한다.
2. 수식의 끝까지 고려했으면 현재 계산 값을 가지고 최댓값을 갱신한다.

 

1. 앞에서부터 차례로 괄호를 하는 경우와 안하는 경우를 모두 고려한다.

 N=19밖에 되지 않으므로 대충 연산자 한 개마다 괄호를 할지 말 지를 결정한다고 쳐도 2^9가지밖에 나오지 않는다. 따라서 완전 탐색으로 풀 수 있다. 앞에서부터 차례로 괄호를 하는 경우와 안하는 경우를 모두 고려해준다.

 괄호를 하지 않는 경우 그냥 순차적으로 가장 앞에 있는 두 수를 계산해주면 된다. 반대로 괄호를 하는 경우에는 맨 앞의 두 수를 연산하지 않고, 두번째 수와 세 번째 수를 먼저 계산한 후, 그 결과와 첫 번째 수를 연산해준다.

 

 

2. 수식의 끝까지 고려했으면 현재 계산값을 가지고 최댓값을 갱신한다.

  괄호를 하지 않는 경우에는 2개의 수를 처리하게 되고, 괄호를 하는 경우에는 3개의 수를 처리하게 된다. 앞에서부터 차례로 위의 그림처럼 더 이상 수가 남지 않을 때까지 처리해주면 된다. 모든 수들을 처리했으면 그 결괏값을 가지고 최댓값을 갱신한다.

반응형

---

#include <iostream>
#include <limits.h>

using namespace std;

int N;
int max_result = INT_MIN;
char mexp[19];

int calc(int a, char op, int b) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
    }
    
    return 0;
}

void brute_force(int idx, int val) {
    if (idx >= N) {
        max_result = max(max_result, val);
        return;
    }
    
    // 1. 괄호 안하는 경우
    char op = mexp[idx];
    int a = mexp[idx+1] - '0';
    
    brute_force(idx+2, calc(val, op, a));
    
    if (idx > N-4) return;
    
    // 2. 괄호 하는 경우
    char op2 = mexp[idx+2];
    int b = mexp[idx+3] - '0';
    int c = calc(a, op2, b);
    
    brute_force(idx+4, calc(val, op, c));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    
    for(int i=0; i<N; i++) {
        cin >> mexp[i];
    }
    
    if (N == 1) max_result = mexp[0] - '0';
    else brute_force(1, mexp[0]-'0');
    
    cout << max_result;

    return 0;
}