BOJ 1541 : 잃어버린 괄호

1541번: 잃어버린 괄호

이 문제는 ‘0~9’, ‘+’과 ‘-‘ 만으로 이루어진 다항식에서 계산 결과가 가장 작은 값을 갖게끔 항의 계산 우선순위를 부여하여 계산하는 문제이다.

예를 들어 다음과 같은 입력이 주어졌을 때,

in : 10 + 30 - 10 + 40 + 30 - 50

다음과 같이 괄호를 묶어 값을 계산해 내면 된다.

out : 10 + 30 - (10 + 40 + 30) - 50 = -90

이 문제에는 정말 쉬운 규칙이 있다.

바로 ‘-‘ 연산을 기준으로 블럭을 나눠 각각의 요소들의 합을 구하여 첫번째 블럭에서 나머지 블럭들을 모두 빼주었을 때, 우리가 원하는 최소값이 만들어진다는 것이다.

이 규칙을 코드로 적용해본다면 다음과 같다.
코드는 Python3의문법을 따른다.

str = input().split('-')
v = []

for s in str :
	tmp = s.split('+')
	cnt = 0
	for n in tmp:
		cnt += n
	v.append(cnt)	

result = v[0]

for i in range(1, len(v)):
	result -= v[i]

print(result)