백준 1541번 잃어버린 괄호 [그리드 알고리즘]

백준 1541번 잃어버린 괄호

양수와 +,- 그리고 괄호를 가지고 식을 만들었는데, 다시 괄호를 다 지운 상태의 값을 입력받는다.

입력 받은 문자열의 값을 가지고 최소한의 값이 나올 수 있도록 프로그램을 작성하자.

 

[문제풀의과정]

1. 최초에는 괄호를 직접 구간별로 넣어서 스택을 활용하여 최소값을 각각 구하는 방식을 고민하였다.
2. 해당 방법은 너무 과정이 복잡한 방법인거 같아서, 다시 고민을 했다.
3. 문제에서 입력 받은 값은 모두 양수라는 점을 뒤늦게 다시 확인을 했고,
   그렇다면 음수가 최초로 발생하는 지점부터 끝까지 모두 음수로 계산이 된다면 최소값을 구할 것으로 예상이 되었다.
4. 3번을 기준으로 코드를 구현하여 문제를 해결했다.

[코드]

str_cals = input().split("-")

result = sum(map(int,str_cals[0].split("+")))
for cal in str_cals[1:]:
    result-=sum(map(int,cal.split("+")))
print(result)

 

•  처음 음수를 기준으로 입력 문자열을 나눈 이유는 음수 이전은 모두 양수의 값을 가지고,
  음수 이후의 발생하는 모든 값들은 전체 값에서 빼야 최소 값을 보장하기 때문이다.