1 분 소요

[Silver II] 잃어버린 괄호 - 1541

문제 링크

성능 요약

메모리: 31120 KB, 시간: 40 ms

분류

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

제출 일자

2024년 4월 10일 16:26:53

문제 설명

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

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

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

입력

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

출력

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

풀이

괄호의 영향을 받는 연산자는 -이다. - 뒤에 오는 연산자들이 영향을 받아서 부호가 바뀐다. 따라서 -로 문자열을 구분해준 후 분리된 각각의 원소들 중 +가 있는 원소 안의 식을 계산한다.

예를 들어 1+2-3-4+5-6 이 주어졌다고 가정해보자. 먼저 -를 기준으로 분리하게 되면 [1+2, 3, 4+5, 6] 로 될 것이다. +가 있는 원소들을 각각 계산해주면, [3, 3, 9, 6]이 된다. 이제 +연산이 모두 사라졌으므로 첫번째 항을 제외한 나머지 값에 -를 붙여 계산하면 최소값을 구할 수 있다. 결과적으로 가정한 식의 최소값은 3 - 3 - 9 - 6 = -15 가 된다.

전체 코드

import sys
input = sys.stdin.readline

polynomial = input().rstrip().split('-') # 입력받은 식에서 -를 구분자로 지정해서 분리
sum_num = [] # 각 원소 안에 합을 계산한 값들을 저장 (마지막에 -연산 수행)

for i in polynomial:
    sum_ = 0
    tmp = i.split('+') # + 기호를 구분자로 분리
    for j in tmp: # + 기호로 구분된 피연산자들의 합을 저장
        sum_ += int(j)
    sum_num.append(sum_) # 합을 저장하는 리스트에 추가
    
answer = sum_num[0] # 첫번째 항을 연산의 초기값으로 지정
for i in range(1, len(sum_num)): # 두번째 항부터 초기값에 -연산을 누적해나감
    answer -= sum_num[i]
print(answer)

댓글남기기

참고