[Python] 백준, 1541 (그리디)

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

1541번: 잃어버린 괄호

그리디 알고리즘?

• 각 상황에서 최선의 선택을 이어나가는 알고리즘
• 마시멜로 게임의 경우 (한시간 참으면 두개 - 당장 받기를 택하면 1개를 제공하는), 각 상황에서 최선의 선택은 1개를 받는 것이므로 절대 2개를 가질 수 없음

개요

• 그리디 알고리즘 분류의 문항
• 로직이나 정보가 크게 과하거나 복잡하진 않음

코드

import sys

seqs = list(map(str, sys.stdin.readline().rstrip('\n').split('-')))
result = []
for seq in seqs:
  sum = 0
  new_seq = seq.split("+")
  for n in new_seq:
    sum += int(n)
  result.append(sum)

answer = result[0]

for n in result[1:]:
  answer -= n

print(answer)

제언

• 괄호의 수가 정해지지 않음을 간과
• 값이 최소가 되려면 + 수식이 붙은 값들은 계산을 완료해주고, 나머지 값들은 마이너스로 계산