[Python] 1541 잃어버린 괄호

문제

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

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

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

입력

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

출력

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

문제 풀이

A. 접근

매번 최적을 찾아야 한다, 탐욕스럽게. 일단 중요한 것은 '-'가 나왔을 때는 괄호로 묶어주는 것이 좋다. 그래야 계속해서 값을 뺄 수 있기 때문이다. 문자열을 통해서 '-'가 나올 때마다 split하는 것이 좋을 것이다. 그렇게 split하면 'A+B'와 같은 구조로 남게 되는데, 이 값들을 총 값에 대해 모두 빼주면 된다.

B. 문제 풀이

전체 코드

q = input().split('-')
ans = 0

for i in q[0].split('+'):
    ans += int(i)

for i in q[1:]:
    for j in i.split('+'):
        ans -= int(j)

print(ans)

B-1. 준비

q = input().split('-')
ans = 0

for i in q[0].split('+'):
    ans += int(i)

가장 먼저 할 것은 마이너스를 살리기 위해서 split으로 문자열을 나눈다. 수학적으로 생각해보면 '55-50-45'라는 문장이 주어졌을 때 55-(50-45)로 괄호를 묶으면 결과적으로 55-50+45로 변하게 된다. 그렇기 때문에 '-'를 기준으로 분리시켜주도록 한다.

그리고 가장 처음으로 등장하는 값들을 먼저 ans에 저장하도록 한다. q[0]으로 설정한 이유는 -를 기준으로 모두 +를 포함하거나 포함하지 않는 값이기 때문이며, 가장 처음 등장하는 값은 초깃값이 되기 때문이다. 그 이후, 다시 '+'를 기준으로 나누어서 더한 값을 저장한다.

B-2. 풀이

for i in q[1:]:
    for j in i.split('+'):
        ans -= int(j)

print(ans)

그 이후로 등장하는 값은 모두 빼주기 위해서 q[1:]를 기준으로 하였고, 그 값들을 '+'로 나누어서 ans에서 값을 빼주도록 했다. 그 이유는 -(a + b)는 결국 - a - b로 변하기 때문이다.

총평

생각해내기 어렵지만 막상 떠올려보면 쉬웠던 문제