괄호 추가하기

아이디어 및 구현 방법

• 괄호가 들어갈 수 있는 경우의 수를 부분집합으로 표현

  • 연산자를 기준으로 했을 때 괄호가 들어간다면 부분집합에 포함
  • 재귀 함수
  • 괄호가 생길때마다 s 리스트에 넣어줌
  • 재귀를 호출하여 처음 들어갈때는 전에 선택된 인덱스+2부터 시작
    • 괄호의 중복을 피하기 위함

• 만들어진 부분집합을 이용하여 연산

  • visited를 이용하여 괄호가 들어가는 연산자의 인덱스 표시

  • 처음 수를 더하고 시작해야하므로 sum을 matrix[0]으로 초기화

  • 연산하기 전 다음 숫자가 괄호가 있다면(visited가 True이면) 괄호부터 계산

    • 연산 수행 후 얻은 값을 피연산자로 이용하여 다시 한 번 연산
    • 두 번의 연산이 모두 끝나고, isPass를 이용하여 다음에 또 연산하지 않게함

  • 앞에서 계산했던 sum을 계속 연산자로 써야함

어려웠던 점

• 부분집합을 만들기 위해 비트 연산을 이용하려 했으나 너무 어려워서 재귀를 이용
• 연산을 수행할 때 sum과 result를 동시에 이용하다보니 연산할 때 헷갈렸음
  • 최대한 sum 하나만을 이용하려고 노력하였음

코드

def subset(here):
    for next in range(here+2,n):
        a.append(next)
        temp = a[:]
        s.append(temp)
        subset(next)
        a.pop()


def operator(y,opcode,x):
    if opcode == '+':
        return y + x
    elif opcode == '-':
        return y-x
    else:
        return y*x


N = int(input())
matrix = list(input())
s = []
for i in range(0,N,2):
    matrix[i] = int(matrix[i])

n = N//2
for i in range(1,n):
    a = [i]
    temp = a[:]
    s.append(temp)
    subset(i)

max = matrix[0]
for i in range(0,N-1,2):
    max = operator(max, matrix[i+1], matrix[i+2])

for i in range(len(s)):
    sum = matrix[0]
    visited = [False]*N
    isPass = False
    for j in range(len(s[i])):
        visited[2*s[i][j]] = True
    for j in range(0, N-1, 2):
        if isPass:
            isPass = False
            continue
        if visited[j+2]:
            result = operator(matrix[j+2], matrix[j+3], matrix[j+4])
            sum = operator(sum, matrix[j+1], result)
            isPass = True
        else:
            sum = operator(sum, matrix[j+1], matrix[j+2])
            isPass = False
    if sum > max:
        max = sum

print(max)