백준 1541 파이썬(그리디)

# 잃어버린 괄호

n = input().split('-')
first = sum(list(map(int,n[0].split('+'))))

for i in range(1,len(n)):
    first -= sum(list(map(int,n[i].split('+'))))

print(first)

 

최소의 값을 만들기 위해서는 처음에 나오는 수 이외에는 모두 빼기로 연산될 수 있도록 괄호를 넣어줘야 한다.

 

- 기호가 나올때마다 괄호를 시작하고 닫아주면 된다.

예를 들어 

 

55-40+30+80이면

55-(40+30+80)

 

55+40-30-50-60+50 이면

55+40-(30)-(50)-(60)+50

 

- 기호가 처음 나올땐 괄호를 열어주고

그 다음 - 기호가 나오면 괄호를 닫아주면 모두 빼는 연산이 된다.

 

*그리디(greedy)

이 문제에서 그리디 개념이 사용된 부분은

최소값을 만들기 위해서는 '+' , '-' 중 '-' 기호가 더 좋으므로

'-'기호만 사용하도록 선택하도록 하는 아이디어가 아닐까 싶다.