Greedy11잃어버린 괄호(1541)

문제

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

입력

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

출력

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

풀이

경우를 생각해 보자.

1-2+3+4+5+6-7
1+2+3+4+5+6-7
1+2+3+4+5+6-7+8
1+2+3+4+5+6-7-8
'-' 가 나타났을 때의 경우를 보면
'-' 뒤의 '+'가 있다면 계속 걔네 끼리는 더해서 몸을 부풀리는게 좋다, 즉 괄호로 묶어주어 크게 한번에 빼는 것이 좋다.
'-' 뒤의 '-' 가 있다면 괄호 없이 빼서 더 작은 수를 만든다.

풀이 !!!

• '-' 기준으로 나누어 원소 저장 5-5+4 라면 '5' '5+4' 로 저장
• '-' 기준으로 나뉘어진 원소에 접근
• '+' 기준으로 나누어 배열에 append
• 첫번째 append 된 원소 기준으로 이후 원소들을 다 빼줌

코드

import sys
sys.stdin = open("input.txt","rt")

def input():
    return sys.stdin.readline().rstrip()


subNum = input().split('-') # '+' 기준으로 나누어 원소 저장 5-5+4 라면 '5' '5+4' 로 저장
cal = []

for i in subNum:
    val = 0
    plusNum=i.split('+')
    for j in plusNum:
        val+=int(j)
    cal.append(val)
stdNum = cal[0]

for j in range(1,len(cal)):
    stdNum -= cal[j]
print(stdNum)

배운 것

• subNum = input().split('-')
  '-'를 기준으로 앞 뒤 원소 저장
• for i in subNum: plusNum=i.split('+')
  subNum이라는 string 원소에 하나하씩 접근하면서 '+'를 기준으로 plusNum이라는 string에 원소 저장

코멘트

split의 쓰임새를 더 알았네