알고리즘 - Python / 백준 - 1541번 : 잃어버린 괄호

1541번: 잃어버린 괄호 (acmicpc.net)

1541번: 잃어버린 괄호

 

---

풀이

• 숫자 , + , - 로만 이루어진 식에 적절히 괄호를 추가해 식의 값이 최소가 되도록 하는 문제이다.
• 떠오른 아이디어는 -가 나오면 다음 -가 나올때 까지의 +와 숫자로 이루어진 식을 묶어 모두 -에 속하도록 처리하는 것이었고 , 이를 통해 문제를 해결하였다.
• 다 풀고나서 코드를 보니 +와 숫자로만 이루어진 식을 계산할 때 , eval() 함수를 사용할 걸 그랬다.
• 문제의 태그를 보니 그리디 알고리즘 등 다양한 태그가 있는 것으로 보아 다른 풀이도 가능한 것 같다.

 

n = input()
n = n.split("-")
ans = 0
for i in range(0,len(n)):
  sub_n = n[i].split("+")
  sm = 0
  for t in range(0,len(sub_n)):
    sm += int(sub_n[t])

  if i == 0:
    ans += sm
  else:
    ans -= sm
print(ans)

---