백준 16638 괄호 추가하기 2

문제 URL : https://www.acmicpc.net/problem/16638

16638번: 괄호 추가하기 2

 

문제 접근법 :  해당 입력값에 괄호를 추가를 하든 말든해서 해당 결과값의 maximum을 구하는 문제입니다.

모든 경우의수를 구하면 되기때문에  n=19라지만 사실상 10으로 봐야합니다. 숫자가 최대 10개이고

모든 경우의수는 2^10  =1024개가 나오기때문에 충분히 풀수있습니다.

그리고 괄호를 숫자 2개만 묶을수있고 중복은 안되니 문제는 더쉬워집니다.

단 연산자우선순위는 *가 더빠르기때문에 *일때를 잘처리해줘야합니다.

 

소스코드 :

#include <bits/stdc++.h>
using namespace std;
long long res=-1e15;
string s;
int n;
long long cal(char c,long long a,long long b){
    if(c=='+')
        return a+b;
    else if(c=='-')
        return a-b;
    else
     return a*b;
}
void dfs(int idx=1,long long before=0,long long sum=0){
    if(idx>=n+1){
        res=max(res,sum);
        return;
    }
    long long num = s[idx]-'0';
    char c=s[idx-1];
    //괄호를 추가안할때
    if(c=='+')
        dfs(idx+2,num,sum+num);
    else if(c=='-')
        dfs(idx+2,-num,sum-num);
    else
        dfs(idx+2,before*num,sum-before+before*num);
    //괄호를 추가할때
    if(idx+2<=n){
        long long num2 = s[idx+2]-'0';
        char c2 = s[idx+1];
        long long acc = cal(c2,num,num2);
        if(c=='+')
            dfs(idx+4,acc,sum+acc);
        else if(c=='-')
            dfs(idx+4,-acc,sum-acc);
        else
            dfs(idx+4,before*acc,sum-before+before*acc);
    }    
}
void input(){
    cin>>n;
    cin>>s;
}
void solve(){
    s="+"+s;
    dfs();
    cout<<res<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    input();
    solve();


}

 

 

이거풀고나서 다른사람코드들을 보려고했는데 파이썬이 많더군요

저는 c++이 익숙해져있었는데 파이썬 코드보고 경악했습니다.

eval()이라는 라이브러리가 존재했고 문자열 수식을 계산해주는 라이브러리가 있다니 놀랠노자라...

기회가 된다면 나중에 파이썬으로 갈아타야하나 생각이 들기도하는 문제였습니다. ㅠ.ㅠ

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.