백준 16637 - 괄호 추가하기 ( 백준 16638, 백준 16639 )

백준 괄호 추가하기 문제입니다. 최근에 기업 알고리즘 테스트를 보는 과정에서 해당 문제를 조금 변형한 문제가 나왔는데, 제대로 풀지를 못했습니다. 일단 이 문제의 풀이가 기억이나서 해당 방식으로 풀어보려고 했으나, 쓰읍.... 역시 제대로 익혀두지 않으면 응용이 안되서  안풀립니다. 풀이를 한번 정리해보고자 합니다.

 

최초 접근

 

입력을 살펴보니 수식의 길이(length)는 '1 <= length <= 19'이고 연산자는 더하기, 빼기, 곱하기 중 하나입니다. 괄호의 경우 중첩된 괄호를 쓸수 없다라고 명시를 하고 있고, 연산은 좌에서 우로 진행하며 연산을합니다. 그런데, 계산기 처럼 *를 먼저 계산하지 않는 부분이 있습니다. 사실 계산기 처럼 계산을 당연히 하겠다고 생각을해서 문자열 계산 함수 eval 같은 것을 구현해서 풀어야 하나 고심을 많이 했습니다. 괄호를 추가할 위치만 완탐하여 위치에 추가하고 eval로 답을 구한다음에 최종적으로 max만 취하는 방법을 찾으려고 했습니다. 근데 일단 eval 자체를 구현하는 것이 어려움이 있었습니다. ( 문자열 계산기 구현 참고 )

 

문자열 길이만 보았을 때 N^2의 연산이 나오는 방식을 채택해도 풀이는 가능하겠다는 판단이 들어서 완탐으로 풀어보고자 하였습니다. 이런 상황에서는 적합하겠다고 생각했는데, 괄호를 추가하는 경우를 생각해보면 0.5초라는 시간 초과가 발생할 수 있겠다는 생각도 들었습니다.

 

 

다시 접근

다시금 생각해보았을 때, 일단 주어진 숫자와 연산자를 쭉쭉쭉 탐색을 해나가는 과정이 반복되는 연산이니까 재귀로 dfs 처럼 풀이를 하면 된다고 생각을 했습니다.

 

그러나 ... 괄호를 추가한다는 부분에서 또 다시 혼선이 왔습니다. ((3+1)*3) 이런식은 또 안된다고 합니다. 음 생각이 복잡한데, 문제에서 주어진 예시처럼 3 + ( 8x7 ) - ( 9x2 ) 이런식으로 계산을 쭉쭉해나가야 하는 구조였습니다. 구조를 도식화 해서 정리를 해보면 아래와 같은 구조가 나오네요. 이렇게 계산을 한다고 하면 중첩된 괄호를 씌울일이 없습니다. 그리고 주어진 문자열 끝에 이른다고 하면, 최종 계산 결과를 비교해서 최대값으로 갱신하면 되는 구조입니다.

 

이게 가능한 이유는 왼쪽에서 오른쪽으로만 계속 연산하기 때문입니다. (일반 계산기 처럼 괄호나, 곱셈, 덧셈 연산을 최우선에 두지 않음 ) 위 풀이를 재귀적으로 구현하면 됩니다. 다만 재귀를 종결하는 조건으로 문자열의 길이를 초과하는지 반드시 체크를 해주어야 하는 문제였습니다.

 

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

// 문자열에서 숫자와 연산자 구분
vector<int> num; 
vector<char> op; 

// 입력
int n = 0;
string s; 

// 출력
int ret = -987654321; // 내가 틀렸던 부분

int oper(char o, int b, int c){
    if(o == '+') return b + c; 
    if(o == '-') return b - c; 
    if(o == '*') return b * c;  
    return 0;
} 

void dfs(int here, int now){

    if(here == (int)(num.size() - 1)){ 
        ret = max(ret, now); 
        return;
    }  
    dfs(here + 1, oper(op[here], now, num[here + 1]));

    if(here + 2 <= (int)(num.size() - 1)){
        int temp = oper(op[here + 1], num[here + 1], num[here + 2]); 
        dfs(here + 2, oper(op[here], now, temp));  
    } 
    return;
} 
int main(){

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

    cin >> n;  
    cin >> s; 
    // 숫자와 연산자 분리, 아래의 경우에는 딱 맞는 수식만 주어지기 때문에 짝수 홀수 index로만 숫자와 연산자 구분이 가능함
    for(int i = 0; i < n; i++){
        if(i % 2 == 0)num.push_back(s[i] - '0');
        else op.push_back(s[i]);
    } 
    
    dfs(0, num[0]);  
    cout << ret << "\n";
    return 0;
}

 

그리고 연산 과정에서 계산 값이 음수가 나올수 있었기에, 최대값으로 갱신해주는 결과를 아예 최소로 잡아주고 업데이트를 해주어야 하는 문제였습니다.

 

생각보다 코드는 안복잡한데 어렵네요. 이 문제 아이디어를 생각하기까지 꽤 오래걸린것 같습니다.

 

---

관련문제

- 백준 괄호 추가하기 2

- 백준 괄호 추가하기 3