[Python] 백준 1541 잃어버린 괄호

문제

 양수와 +, -, 그리고 괄호를 가지고 식을 만든 후, 다시 괄호를 지웠다. 다시 괄호를 쳐서 값을 최소로 만드는 문제이다.

 

 

 

입력

• ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어진 식(처음과 마지막은 숫자)

 

 

출력

최솟값

 

 

 

 

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

1541번: 잃어버린 괄호

---

★Keypoint : 그리디 알고리즘 , sys

 

그리디 알고리즘을 사용하면, 각 '+' 연산 이후에 나오는 수는 '-'로 빼주면서 최소값을 만들 수 있다

EX)

입력으로 55 - 50 + 40 가 들어왔을 때 55 - ( 50 + 40 ) 을 해야 최솟값인 -35이 나오는 것이다.  

 

따라서 '-'을 기준으로 수식을 나누는 것은, 각각의 부분 식에서 '+' 연산을 먼저 계산하고 그 이후에 '-'로 빼주는 것이 최소값을 만들기에 적절한 것이다.

 

 

<최종 CODE>

expression = input().strip().split('-')

result = sum(map(int, expression[0].split('+')))
for exp in expression[1:]:
    result -= sum(map(int, exp.split('+')))

print(result)

 

•  

 

1. expression = input().strip().split('-'): 입력된 수식을 '-'를 기준으로 나누어 리스트로 만들기
2. result = sum(map(int, expression[0].split('+'))): 첫 번째 부분은 '+'로만 구성되어 있으므로 이를 더하기
3. for exp in expression[1:]: result -= sum(map(int, exp.split('+'))): 나머지 부분은 '-'가 나오면 그 이후의 모든 값을 빼주는 그리디한 방식으로 계산
4. print(result): 최종 결과를 출력