[PYTHON] 백준 1541 - 잃어버린 괄호

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

성능 요약

메모리: 113248 KB, 시간: 112 ms

분류

그리디 알고리즘, 수학, 파싱, 문자열

문제 설명

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

---

아이디어, 문제풀이

• • 를 기준으로 나눌것인지, + 를 기준으로 나눌것인지, 둘 다를 기준으로 나눌것인지
• 최소값을 만들어야 하기에, - 제외한 나머지 수식들에 괄호를 쳐주면 큰값을 빼낼 수 있다. - 를 기준으로 나눈다.

---

TROUBLE SHOOTING

• 이 문제도 앞선 동전 문제처럼 어려운 부분은 없었는데, 수식을 구현할때, str을 int로 바꿔주는 과정을 쉽게 캐치해 내진 못했다. 그 외엔 어렵지 않게 풀었던 것 같다.

---

코드

#https://www.acmicpc.net/problem/1541
#잃어버린 괄호
#1541

import sys
input = sys.stdin.readline

n_list = list(map(str, input().strip().split('-')))

# print(n_list)

def fun(n_list):

    result = 0

    for i in range(len(n_list)):
        plus_result = 0
        plus_list = []

        plus_list = n_list[i].split('+')
        # print(plus_list)

        for j in range(len(plus_list)):
            plus_result += int(plus_list[j])
        
        # print(plus_result)

        if i == 0:
            result += plus_result

        else:
            result -= plus_result

    return result

answer = fun(n_list)
print(answer)