[DP] 1541번 : 잃어버린 괄호

문제 

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

출제 문제 : https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

---

해결 방법

잃어버린 괄호 문제 내용은 입력으로 주어진 부분을 신경쓰는게 포인트인 것 같다. 주어진 조건에 보면 식은 '0' ~ '9', '+', '-' 만으로 이루어져 있으며 맨 처음과 마지막은 숫자라고 한다.

 

처음에는 스택을 사용하여 flag로 +, - 를 해주는 방법과 eval() 함수를 사용하는 2가지 방법을 생각해 보았는데 좀 더 고민해 보니 split()을 이용하여 '-'를 기준으로 나누는 것이 좀 더 구현하기 편할 것 같다는 생각이 들었다.

 

만약, 예를 들어 30-20+30+40-20+30가 있다면 '-' 가 나온 후 다음 '-'가 나오기 전까지 괄호를 쳐야 가장 작은 값을 만들 수 있다. 정리를 하자면 30-(20+30+40)-(20+30)으로 구현하면 식의 값을 최소로 만들 수 있을 것이다. 이 방법을 생각하며 아래 코드를 작성해 보았다.

 

[코드]

import sys

datas = sys.stdin.readline().rstrip().split('-')

result = 0
# '-' 가 없을 경우
if len(datas) == 1:
        temp = datas[0].split('+')
        print(sum(list(map(int,temp))))

# '-' 가 한 개 이상 있을 경우
else:
    # 배열 첫번째 데이터 temp에 저장(유일한 '+' 연산)
    temp = sum(list(map(int,datas[0].split('+'))))
    for i in range(1,len(datas)):
        # 결과 값 '-' 진행 
        result-=sum(list(map(int,datas[i].split('+'))))
    # 전체 결과에서 temp '+' 연산
    print(result+temp)

처음에는 '-' 가 없는 경우를 생각하지 않고, 구현했더니 조건에 충족하지 못했다.

 

따라서, '-'가 있는 경우와 없는 경우를 나누어 구현했다.

 

여기서 주의할 점은 첫번째 데이터를 따로 계산해야 한다는 점인데 만약 for문을 0부터 시작한다면 sum에서 유일한 양수인 첫 배열 데이터가 '-'로 연산되기 때문에 처음에 따로 빼놓고, 이후에 추가로 계산해줬다.