[BOJ] 1541번: 잃어버린 괄호 (Greedy)

 

 

문제 링크

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

 

 

TIL

• 문제를 잃고  처음에는 어떻게 풀어야하나 고민했으나 '-'가 중요한 역할이라고 생각했다.
  • -가 나오지 않는 이상 무조건 +이므로 다 더해질 것이고,
    -가 나오면 그 뒤에 오는 모든 숫자는 그 다음 -가 나오기 전까지 모두 더하는 것이 가장 큰 수를 뺄 수 있는 방법이라고 생각
  • 그래서 -를 기준으로 분할을 하고, 분할한 것들을 +를 기준으로 분할하여 숫자를 구했다
  • 파이썬의 매우 유용한 기능 split 사랑훼
• 이 방법이 왜 그리디인지??
  • 그리디 알고리즘에서는 현재 상태에서 가장 좋은 선택을 계속해서 취하고 그 선택들이 합쳐져서 최적의 해를 만든다고 가정한다
  • 이 문제에서도 - 연산자를 기준으로 수식을 나누고, 나누어진 후에는 각각의 부분을 최대한 최소화하려는 선택을 계속해서 하므로, 그리디 알고리즘을 적용했다고 할 수 있다
• 처음에는 당황했으나 차분히 생각하여 5분도 안걸려서 풀었던 문제

 

Code

temp = list(input().split('-'))
t_len = len(temp)

operand = []
for t in temp:
    nums = list(map(int, t.split('+')))
    operand.append(sum(nums))
if len(operand) >0 :
    ret = operand[0]
    for i in range(1, len(operand)):
        ret -= operand[i]

print(ret)