[그리디] 백준 1541번: 잃어버린 괄호

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

1541번: 잃어버린 괄호

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다

www.acmicpc.net

그리디 유형의 문제고, 답을 어떻게 낼지 생각을 해야한다.

괄호를 원하는 만큼 칠 수 있는 상황이라면, 다음이 가능하다.

예를 들어

10+20+30-40+50+60-70-80+90-100가 있을 때

괄호를 적절히 쳐서 최솟값을 만들어보면 다음과 같이 된다.

10+20+30-(40+50+60)-70-(80+90)-100

즉 식을 10+20+30-40-50-60-70-80-90-100으로 만들 수 있다.

여기서 깨달아야 할 점은 한번 마이너스 부호가 등장한 이후부터는

모든 연산이 마이너스가 되도록 만들 수 있다는 것이다. 왜냐면 나는 괄호를 맘껏 칠 수 있으니깐.

따라서 답은 -가 나올때까지 계속 더해주다가 -가 등장한 순간부턴 계속 빼주면 된다.

import re
string = input()
if '-' in string:
    left, right = string.split('-',1)
    left = sum(map(int, re.sub('[+]',' ',left).split()))
    right = sum(map(int, re.sub('[+-]',' ',right).split()) )
    print(left-right)
else:
    print(sum(map(int, re.sub('[+]',' ',string).split())))