[백준] #1541 잃어버린 괄호(python)

📌문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 정답을 출력한다.

예제 입력1

55-50+40

예제 출력1

-35

예제 입력2

10+20+30+40

예제 출력2

100

예제 입력3

00009-00009

예제 출력4

0

백준 1541번 문제

💡Idea

괄호를 씌운다는 것은, 무엇을 먼저 계산할지를 결정한다는 의미입니다.

따라서 이 문제는 덧셈과 뺄셈만이 존재하는 식에서, 각 덧셈과 뺄셈의 순서를 결정해서 최솟값을 만들어내는 문제입니다.

그럼 최솟값을 만드려면 무엇을 계산해야 할까?🤔

최대한 작은 숫자를 만들기 위해서는, 최대한 큰 수들을 만들어서 계속 빼주면 됩니다.

최대한 큰 수를 만들어서 빼는 방법은 아래👇와 같습니다.

1. 덧셈을 먼저 모두 수행한다.
   1+2-3-4+5+6+7-8 의 경우, (1+2)-3-(4+5+6+7)-8 = 3-3-22-8
2. 남은 뺄셈 계산을 수행한다.
   3-3-22-8 = -30

💻코드

• ⏰ 시간 : 68 ms / 메모리 : 30840 KB

import sys
exp = [sum(map(int, e.split('+'))) 
	   for e in sys.stdin.readline().strip().split('-')]
ans = exp[0] # 가장 앞의 숫자에서 나머지 숫자들을 빼줌
for i in range(1, len(exp)): # 첫번째 요소 제외 뺄셈
    ans -= exp[i]
print(ans)

📝코드 설명

변수

• exp : 뺄셈을 기준으로 분할한 뒤, 각 요소들을 다시 덧셈을 기준으로 분할하여 해당 숫자들을 모두 더한 리스트로, 예를 들어 1+2-3-4+5+6+7-8인 경우 [1+2, 3, 4+5+6+7, 8] -> [[1, 2], [3], [4, 5, 6, 7], [8]] -> [3, 3, 22, 8]의 과정을 거쳐 저장이 됩니다.
• ans : 최솟값 결과 저장하는 변수