[백준] 16637 괄호 추가하기

문제 주소 : www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

문제 확인

 

수식의 길이가 짧기 때문에 간단하게 dfs로 풀 수 있습니다.

계산한 값이 기록되어 있어야 하므로 스텍과 함께 탐색합니다.

 

풀이

 

괄호 연산자는 우선순위를 부여하는 연산이므로 스텍을 이용하여 우선순위에 따라 계산을 진행할 수 있습니다. dfs 완전 탐색 시 2가지의 탐색 경로가 있습니다.

1. 현재 수식을 계산합니다. = 괄호 없이 진행 or 현재 수식에 괄호를 둠
2. 현재 수식을 계산하지 않고 스텍에 넣어둡니다. = 다음 수식에 괄호를 둠

중복 괄호를 두지 않도록 bool 변수를 통해 전단계에서 괄호를 삽입하였다면 다음 단계에서는 괄호를 삽입하는 탐색은 넘어갑니다.

 

코드

#include <cstdio>
char a[20], o[9];
int N, m = -0x7FFFFFFF, n[10], e=0;
inline int clc(char o, int x, int y){
    switch(o){case '+':return x + y;case '-':return x - y;case '*':return x*y;}
}
void dfs(int c, bool f) {
    if(c==N){
        int v=n[0];
        for(int i=0; i<e; i++) v=clc(o[i], v, n[i+1]);
        if(v>m)m=v;
        return;
    }
    if(f){
        int t=n[e];
        n[e]=clc(a[c],n[e],a[c + 1]-48);
        dfs(c+2,false);
        n[e]=t;
    }
    o[e]=a[c];
    n[++e]=a[c+1]-48;
    dfs(c+2,true);
    e--;
}
int main(){
    scanf("%d%s",&N,a);
    n[0]=a[0]-48;
    dfs(1,true);
    printf("%d",m);
}