백준 16637번. 괄호 추가하기(c++) / 문자열 처리

카카오에서 나올 법한 문자열 처리 문제였다.

숫자를 기준(idx)으로 idx+2값이 전체 문자 전체의 길이에 벗어나지 않는다면, 괄호를 추가하거나 추가하지 않는다.

 

1) 괄호를 추가한다면, idx(숫자), idx+1(연산자), idx+2(숫자) 값을 계산해준 다음 그 전까지의 총합과 계산하여 넘겨주었다.

그리고 다음 idx값은 idx+4가 된다.

2) 괄호를 추가하지 않는다면, 그 전까지의 총합과 지금 값을 연산해주고 다음 숫자로 넘어간다.

 

코드를 보면 더 이해가 잘 될 것이다.

 

코드 첨부

// 괄호 추가하기
#include <iostream>
#include <vector>
#include <stack>
#include<climits>
using namespace std;
 
int n;
string s;
int final = INT_MIN;
 
int cal(int a, int b, char oper)
{
    int result = a;
    if(oper=='+'){
        result += b;
    }else if(oper=='*'){
        result *= b;
    }else{
        result -= b;
    }
 
    return result;
}
 
 
void dfs(int idx, int total){
    if(idx>s.size()-1){ // 종료
        // 최대값 갱신
        final = max(final, total);
        return;
    }
 
    char oper;
    if(idx==0){
        oper = '+';
    }else{
        oper = s[idx-1];
    }
 
    // 괄호 추가하기
    if(idx+2<s.size()){
        int temp = cal(s[idx]-'0', s[idx+2]-'0', s[idx+1]);
        dfs(idx+4, cal(total, temp, oper));
    }
 
    // 괄호 추가 안한다.
    dfs(idx+2, cal(total, s[idx]-'0', oper));
}
 
int main()
{
    cin>>n;
    cin>>s;
 
    dfs(0, 0);
    cout<<final<<"\n";
    return 0;
}

 

 

문제 첨부

https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

github 첨부

https://github.com/jungahshin/algorithm/blob/master/c:c%2B%2B/16637_review.cpp

jungahshin/algorithm