[Python/파이썬] 백준 1541 - 잃어버린 괄호

문제 설명

 

입출력 예제

 

---

풀이 코드

그리디 알고리즘 문제로 괄호를 적절히 합쳐서 최소 값이 나올 수 있게 하는 방법만 알면 쉽게 해결할 수 있다.

해당 방법는 모든 + 식들만 먼저 더하고 나중에 구한 값들을 첫 번째 값에서 부터 빼는 방식이다.

이때, 첫 번째 값은 등호가 없으므로 따로 저장하여 처리한다.

 

만약 10 - 20 + 30 - 60 + 20 - 40 이 주어졌다고 가정해보자.

가장 최소 값이 나올 수 있도록 덧셈 식들만 괄호를 적용하면 다음과 같다.

(10) - (20 + 30) - (60 + 20) - (40)

이 식대로 계산을 하면 정답은 10 - 50 - 80 - 40 = -160이 된다.

 

정답 코드

import sys
input = sys.stdin.readline
arr = input().split('-')

num = 0
for i in arr[0].split('+'):
    num += int(i)
for i in arr[1:]:
  num -= sum(map(int, (i.split('+'))))
print(num)