[백준 16637번] 파이썬 - 괄호 추가하기

백준 16637_괄호 추가하기

시간 제한 0.5초(추가 시간 없음), 메모리 제한 512MB

# 조건

• 길이가 N인 수식이 있다.
• 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다.
• 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.
• 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다.
  • 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다.
  • 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다.
  • 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.
• 수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오.
• 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입력

• 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다.
• 둘째 줄에는 수식이 주어진다.
• 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다.
• 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다.
• 연산자는 +, -, * 중 하나이다. 여기서 * 는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

출력

• 첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다.
• 정답은 2^31보다 작고, -2^31보다 크다.

# 접근 방법

• 우선 입력을 받으며 lambda를 활용해준다.
  • isdigit이라면 int, 아니라면 문자열로 받아준다.
• 또한, 수식의 길이가 1이라면 바로 출력, 아니라면 dfs 함수를 돌려준다.
• 주의할 점 !!
  • 연산자는 무조건 홀 수 번째 인덱스에 위치
  • 왼쪽부터 순서대로 계산하므로 첫 번째 여는 괄호는 첫 번째 연산자 바로 뒤부터 올 수 있다.
  • 닫는 괄호는 여는 괄호의 위치에서 숫자, 연산자, 숫자를 지나서 위치하므로 현재 여는 괄호의 위치 + 3이 전체 길이보다 작은 경우에만 괄호를 열고 닫을 수 있다.
    • 이를 활용하여 범위를 벗어난다면 괄호를 열지 않고 계산 해주고
    • 아니라면 현재 연산자 위치 다음에 나오는 연산자에 대해 괄호를 묶어서 계산해준다.
  • 또한, 괄호로 묶지 않고 계산하는 경우도 dfs를 통해 연산해주면 된다.
• dfs 함수
  • 테스트 케이스 1번을 예시로 들면
  • +에서 시작하여 dfs를 돌려준다.
  • 8 * 7 을 괄호를 쳐주어도 범위 내이므로 calc의 num2 인자로 먼저 계산 해주고, 연산 결과를 3 + 와 다시 calc 함수를 해준다.
  • idx인자에는 + 와 * 까지 계산했으므로 다음 연산자는 - 가 되고 인덱스는 현재 1번 + 4 = 5가 되며 prev 인자에는 3 + (8 * 7) = 59가 들어간다.
  • 9 * 2에도 괄호를 사용할 수 있으므로 위와 마찬가지로 9 * 2를 먼저 calc로 계산하고 이전의 59 - (9 * 2) 를 계산해주면 된다.
  • 이후의 idx는 N 이상이므로 재귀에서 돌아와 처음의 +를 괄호를 사용하지 않은 연산을 수행해주면 된다.

def dfs(idx, prev):  
    global result  
    if idx >= N:  
        result = max(result, prev)  
        return  
    if idx + 3 < N:  
        # 괄호 계산  
        dfs(idx+4, calc(prev, calc(array[idx+1], array[idx+3], array[idx+2]), array[idx]))  
    # 괄호 x 계산  
    dfs(idx+2, calc(prev, array[idx+1], array[idx]))

전체 코드

import sys  
sys.stdin = open('input.txt')  
N = int(input())  
array = [*map(lambda x:int(x) if x.isdigit() else x, input())]  
result = -int(1e9)  

def calc(num1, num2, s):  
    if s == '+':  
        return num1+num2  
    elif s == '-':  
        return num1-num2  
    else:  
        return num1 * num2  

def dfs(idx, prev):  
    global result  
    if idx >= N:  
        result = max(result, prev)  
        return  
    if idx + 3 < N:  
        # 괄호 계산  
        dfs(idx+4, calc(prev, calc(array[idx+1], array[idx+3], array[idx+2]), array[idx]))  
    # 괄호 x 계산  
    dfs(idx+2, calc(prev, array[idx+1], array[idx]))  

if N == 1:  
    result = array[0]  
else:  
    dfs(1, array[0])  
print(result)