백준 16637 괄호 추가하기

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

16637번: 괄호 추가하기

문제 확인

 

dfs풀이, 연산자 우선순위가 동일 하기 때문에 단순 완전 탐색으로 풀 수 있다.

 

풀이

 

연산자 우선순위가 없기 때문에 현재 식을 계산하면 스텍 top의 값만 변경, 계산하지 않으면 스택에 push 합니다.

괄호 중첩을 빼기 위해 전 단계에서 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);
}