브루트포스) 16637.괄호 추가하기

16637번: 괄호 추가하기 (acmicpc.net)

16637번: 괄호 추가하기

# solution.
# 비트마스크, 브루트포스 문제
# 연산자의 개수 m=(n-1)/2 이고, n은 19 이하이므로, m의 최댓값은 9다.
# 시간복잡도 : 각 연산자가 괄호에 포함되는지 아닌지로 구분되기에, 모든 경우의 수는 최대 2^9=512 이다.
# 각 자리의 연산자가 포함되면 1로, 포함되지 않으면 0으로 생각하여, 비트마스크로 구분한다.
# 각 괄호는 연산자를 하나만 포함할 수 있으므로, 연산자 비트마스크의 모양은 010, 101, 100, 000 등 1이 연속되지 않을 때 가능하다.

n=int(input())
a=list(input())
# 숫자의 경우 int형으로 변환
for i in range(0,n,2):
    a[i]=int(a[i])
ans=int(-1e9)
# 연산자의 개수 m=(n-1)/2
m=(n-1)//2

# 모든 연산자의 포함 여부를 대상으로 전체 경우의 수를 완전탐색
# 각 자리의 연산자가 포함되면 1로, 포함되지 않으면 0으로 생각하여, 비트마스크로 구분한다.
for s in range(1<<m):
    # 중복 괄호 여부
    ok=True
    for i in range(m-1):
        # 괄호에 포함되는 연산자 2개가 연속이면 중복 괄호다.
        if s&(1<<i)>0 and s&(1<<(i+1))>0:
            ok=False
    # 중복 괄호 아니면 진행
    if not ok:
        continue
    b=a[:]
    # 연산자가 괄호에 포함되어 있으면, 괄호 내에서 해당 연산자를 적용한 결과를 왼쪽 숫자에 놓고, 오른쪽 숫자는 0으로 만들고, 해당 연산자는 +로 만든다.
    for i in range(m):
        if s&(1<<i)>0:
            k=2*i+1
            if b[k]=='+':
                b[k-1]+=b[k+1]
                b[k]='+'
                b[k+1]=0
            elif b[k]=='*':
                b[k-1]*=b[k+1]
                b[k]='+'
                b[k+1]=0
            else:
                b[k-1]-=b[k+1]
                b[k] = '+'
                b[k+1]=0
    # 수식의 첫째 숫자부터 차례대로 연산자를 적용해 결과를 구한다.
    res=b[0]
    for i in range(m):
        k=2*i+1
        if b[k]=='+':
            res+=b[k+1]
        elif b[k]=='*':
            res*=b[k+1]
        else:
            res-=b[k+1]
    ans=max(ans,res)
print(ans)