[Algorithm] BAEKJOON 1541번: 잃어버린 괄호 (Python)

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

 

 

 

 

문제

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

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

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

 

입력

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

 

출력

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

 

 

 

 

 

풀이

수식을 마이너스 기호 기준으로 나누고 마이너스 기호 이후에 나오는 숫자들을 모두 더한 후 이를 한 번에 빼서 수식의 값을 최소화 하는 그리디 전략을 적용하여 해결하였다.

 

 

Python 소스 코드

def minimize_expression(expression):
    # '-'를 기준으로 식을 나눈다
    parts = expression.split('-')

    # 첫 번째 파트는 모두 더한다
    first_sum = sum(map(int, parts[0].split('+')))

    # 나머지 파트는 모두 더한 후 빼준다
    rest_sum = sum(sum(map(int, part.split('+'))) for part in parts[1:])

    # 최종 결과는 첫 번째 합에서 나머지 합을 뺀 값
    return first_sum - rest_sum


# 입력 받기
expression = input()

# 결과 출력
print(minimize_expression(expression))