백준 s2 1541 잃어버린 괄호 c++

 

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

풀이

 

처음에는 괄호를 한 번만 칠 수 있는 줄 알고 이걸 어떻게 그리디로 풀지 .. 고민했으나 괄호는 그냥 마음대로 칠 수 있는 거였다.

괄호를 제한없이 칠 수 있으면, -뒤에 오는 숫자들에 괄호를 쳐서 최대한 많이 빼주면 최솟값이 될 거라 예상할 수 있다.

 

-뒤에 오는 +들에 괄호를 치면 -를 분배한 것들과 같다. 다음 -가 오기전까지 +들을 묶어서 빼줄 값이 최대가 되도록 하면 된다.

 

코드

/*boj s2 1541 잃어버린 괄호*/
#include <iostream>
#define MAXN 105
using namespace std;

string S;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> S;
    string num = "0";
    int res = 0;
    bool minus = false;
    for (char s : S) {
        if (s == '-') { // 다음 -가 오기 전까지, 뒤에 오는 애들 다 더한만큼 뺌
            if (minus)
                res -= stoi(num);
            else
                res += stoi(num);
            num = "0";
            minus = true;
        } else if (s == '+') {
            if (minus)
                res -= stoi(num);
            else
                res += stoi(num);
            num = "";
        } else { // 숫자
            num += s;
        }
    }
    if (minus) {
        res -= stoi(num);
    } else {
        res += stoi(num);
    }
    cout << res << "\n";
}