BOJ 1541, 잃어버린 괄호

문제

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

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

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

입력

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

출력

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

탐욕법으로 풀 수 있는 대표적인 문제이다.

이 문제를 푸는 방법은, -가 등장할 때마다 괄호를 쳐주면 된다는 것이다.

예제로 55-50+40-32+27+35-7-100-23 가 입력으로 주어졌다고 해보자.

55 - (50 + 40) - (32 + 27 + 35) -7 -100 -23 이 최선의 괄호 선택이 될 것이다.

이 문제는 사실 그리디 알고리즘으로 풀 수 있는지 없는지를 묻는

문제이기도 하지만, 사실 문자열 처리를 어떻게 하냐를 묻는 문제이기도 하다.

C, C++의 경우, scanf(" %c%d",&sign, &num); 으로 입력을 받으면,

맨 앞의 문자를 제외하고 "부호""숫자"의 형태로 입력을 받을 수 있다.

다만, %c앞에 스페이스바를 하나 붙여줬는데 스페이스바가 있으면 "엔터"까지 받아버리는

불상사를 면할 수 있다. (화이트 스페이스 제거)

꼭 알아두도록 하자.

#include <cstdio>
#include <cmath>
#include <iostream>
 
using namespace std;
 
int main() {
    int val[26], N = 0, result = 0, i;
 
    for (i = 0; scanf("%d", val + i) > 0; i++) N++;
    for (i = 0; i<N && val[i] >= 0; i++) result += val[i];
    for (; i<N; i++) result -= abs(val[i]);
 
    printf("%d\n", result);
}