1541 잃어버린 괄호

덧셈과 뺄셈으로 이루어진 식이 주어질 때, 원하는곳에 괄호를 넣어 식의 값을 최소로 하려고 한다. 이 때의 최솟값을 구하는 문제이다.

생각해보면 뺄셈이 나온 순간부터 무조건 빼주기만하면 된다는걸 알 수 있다.

따라서 뺄셈이 나오기전까진 계속 더해주다가, 뺄셈이 나오는순간 그 다음 식은 전부 빼주면 된다.

소스