백준 1541 잃어버린 괄호 - 파이썬

import sys
input = sys.stdin.readline

exp = input().rstrip().split('-') 
arr = []

for i in range(len(exp)):
  temp = 0  
  for t in exp[i].rstrip().split('+'):
    temp += int(t)
  arr.append(temp)

res = arr[0]
for a in arr[1:]:
  res -= a

print(res)

 

최솟값을 찾는 기준을 잘 모르겠어서 고민하다가 검색해서 알아낸 , , 답 

괄호를 적절히 쳐서 값을 최소로 만드는 방법은, 핵심적으로 '-' 연산자를 기준으로 나누는 것

이렇게 하면 '-' 연산자를 기준으로 나눠진 부분들을 먼저 더한 후, 마지막에 뺄셈을 수행하여 값을 최소화할 수 있음

 

1. 식을 '-' 연산자를 기준으로 나눈다.
2. 나눠진 부분 더하기 > 각 부분 문자열에 대해 '+' 연산자를 기준으로 더한다.
3. 처음 부분은 더한 값을 초기값으로 두고, 그 다음 나머지 더한 값들을 뺀다.

 

 

 

예를 들어, 입력이 "55-50+40-30+20+10"이라면,

1. "-" 기준으로 나누기 > ["55", "50+40", "30+20+10"]
2. 나눠진 부분 더하기
   
   • "55" → 55
   • "50+40" → 90
   • "30+20+10" → 60
3. 첫 번째 값에서 나머지 값들을 빼줍니다:
   • 55 - 90 - 60 = -95

결과적으로, 최소값은 -95