백준 #1541

 

괄호를 잘쳐서 최소값으로 만드는 문제.

-를 만나면 다음 -를 만날때까지 괄호를 치는게 최적의 해이다. 원래는 그리디 알고리즘으로 정당성을 증명해야하지만 그냥 직관적으로 봐도 자명한 사실이라 생략한다. 

 

import sys

fomula = list(map(str,sys.stdin.readline().split('-')))

def listsum(lst):
    lst1=str(lst).split('+')
    sum = 0
    for i in lst1:
        sum+=int(i)
    return sum

sum = 0
sum +=listsum(fomula[0])
for i in range(1,len(fomula)):
    sum-=listsum(fomula[i])

print(sum)

파이썬에는 신기하고 편리한 방법이 많은거같다.