백준 1541번: 잃어버린 괄호 [python]

https://www.acmicpc.net/problem/1541

문제 접근

괄호가 없는 식에 괄호를 쳐서 가장 최소로 값을 만드는 문제.

"-" 뒤에 오는 모든 숫자들을 괄호로 묶어서 한 번에 빼면 최소값이 된다.

왜냐하면 괄호를 적절히 친다. 라는 것은
a - b + c - d + e
를 최소로 만들려면
a - (b + c) - (d + e) 이지만 결국
결괏값은 a - ( b + c + d + e ) 와 동일하기 때문이다.

해답 및 풀이

# 수식을 입력받아 '-' 기준으로 나눈다
parts = input().split('-')

# 첫 번째 부분은 괄호로 묶을 수 없으므로 무조건 더한다
total = sum(map(int, parts[0].split('+')))

# 두 번째 덩어리부터는 괄호로 묶어서 전체를 빼주는 게 최소값을 만든다
for part in parts[1:]:
    total -= sum(map(int, part.split('+')))

print(total)