[알고리즘 풀이 분석] BOJ 16637 괄호 추가하기

오늘 풀어본 문제는 골드 3 레벨 BOJ 16637 괄호 추가하기 이다! 오늘의 문제 에서 뽑아서 풀었고 사실 어제 도전한 문제지만,, 어제 별안간 공부를 때려치고 저녁시간을 놀아버렸다가 오늘 책상에 앉자마자 얼른 해결하였다!

BOJ 16637 괄호 추가하기

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입출력

나의 풀이

문제의 시간 제한이 좀 타이트 했기 때문에 어제 문제를 풀려고 끄적일때는 아 이건 DP 문제구나! 라고 자신있게 생각했다 ^^,, 물론 DP 로 풀 수도 있겠지만 결론 적으로는 재귀함수를 이용해 풀었고 관련 알고리즘은 BruteForce 가 적혀있었다.

문제 조건에 따르면 괄호는 중첩될 수 없다. 한번 괄호로 묶으면 반드시 다음 연산자에는 괄호가 적용될 수 없도록 해야 하고 그 다음 연산자부터 괄호가 적용될 수 있다.

입력으로 들어오는 수식 formula 를 앞에서 뒤로 탐색하고, 직전에 괄호가 적용이 되었는지를 나타내는 bracket, 연산한 부분 결과값 result 를 매개변수로 하여 함수 addBracket 를 재귀 호출하였다!

주의해야 할 점은, 현재 curr 변수가 가리키고 있는 연산자에 대해서 괄호를 추가하려고 한다면 직전에 계산된 과정을 되돌린 후 새롭게 연산을 해 주어야 한다는 점이다.

현재 curr 가 가리키고 있는 곳에 괄호를 추가해 아래 수식처럼 연산을 진행하려 한다면 3+8 = 11 이었던 result 를 8이 더해지기 이전의 결과 3으로 되돌리고 해당 값과 8과 7을 괄호로 묶은 값 bracket(56) 을 직전에 사용된 연산자 lastMethod('+') 로 다시 연산해 주어야 한다.

또한 이 과정에서 0으로 나누는 경우가 생기는 것을 방지해 현재까지의 누적 결과들을 저장하는 배열 memo를 사용하였고 만약 0으로 나누는 경우가 발생된다면 누적 결과를 memo[curr-3] 에서 가져와 연산을 진행하도록 주의하였다!

전체 코드

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

// BOJ 16637 괄호 추가하기, 브루트포스 ,골드 3
using namespace std;

int N;
string formula;
int MAXIMUM = -2147483648;  // 최종 결과 값 

// 반대 연산자 반환 
char getOpposite(char method){
    switch (method) {
        case '+':
            return '-';
        case '-':
            return '+';
        case '*':
            return '/';
        case '/':
            return '*';
    }
}

// 계산 함수 
int calculate(int a, int b, char method){
    switch (method) {
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        case '/':
            return a/b;
    }
}

// 재귀함수 
void addBracket(int result, int curr, bool bracket, vector<int> memo) {
    if (curr > N-1){  // 종료조건
        if (result > MAXIMUM) MAXIMUM = result;
        return;
    }

    // 현재 연산자에 괄호 추가 X 
    int newResult = calculate(result, formula[curr+1]-'0', formula[curr]);
    memo[curr+1] = newResult;
    addBracket(newResult, curr+2, false, memo);

    // 이전에 괄호 없었다면 괄호 추가 가능 
    if (!bracket){  
        int lastNumber = formula[curr-1]-'0';
        char lastMethod = formula[curr-2];  // 직전 연산자 
        char opposite = getOpposite(lastMethod); // 반대 연산자 

        int lastResult;  // 되돌린 결과 값 
        if (opposite == '/' && lastNumber ==0){  // divided by 0 방지 하기 
            lastResult = memo[curr-3];
        }else{
            lastResult = calculate(result, lastNumber, opposite);
        }
        int bracketed = calculate(lastNumber, formula[curr+1]-'0', formula[curr]);  // 괄호 추가시 괄호 안 결과
        lastResult = calculate(lastResult, bracketed, lastMethod);  
        
        addBracket(lastResult, curr+2, true, memo); // 재귀함수 호출 
    }
}

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

    cin>>N>>formula;

    vector<int> memo(N, 0);

    if (N==1){
        MAXIMUM = formula[0]-'0';
    }else{
        int start = calculate(formula[0]-'0', formula[2]-'0', formula[1]);
        memo[0] = formula[0]-'0';
        memo[2] = start;

        addBracket(start, 3, false, memo);
        addBracket(start, 3, true, memo);
    }
    cout<<MAXIMUM;

    return 0;
}