1541 잃어버린 괄호

그리디 알고리즘으로 푸는 문제이다.

괄호를 무한히 맘대로 사용할 수 있다.

-가 나온 뒤에

+가 나온다면 다 괄호로 묶고,

-가 나온다면 새로 괄호를 시작하여 뒤에 +를 다 묶으면 된다.

즉 -가 나오면 그냥 다 빼주면 된다.

그 순간의 최적해가 전체의 최적해가 되는 구조인 문제.

논리적으로 이게 정답이 나올지 잘 생각해보아야 한다.

그게 보장이 된다면,

greedy algorithm으로 해를 구할 수 있다.

+는 상관없이 계속 더하면 되지만, -가 나오면 그 다음으로 나오는 수는 다 빼주면 된다.

#include <iostream>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    bool minus_check = false;
    int start = 0;
    int ans = 0;
    for (int i=0; i<s.size(); ++i){
        if (s[i] == '+') {
            ans += stoi(s.substr(start, i - start));
            start = i + 1;
            continue;
        }
        if (s[i] == '-'){
            ans += stoi(s.substr(start, i - start));
            start = i + 1;
            minus_check = true;
            break;
        }
    }
    if (minus_check){
        for (int i=start; i<s.size(); ++i){
            if (s[i] == '+' || s[i] == '-'){
                ans -= stoi(s.substr(start, i - start));
                start = i + 1;
                continue;
            }
        }
        ans -= stoi(s.substr(start, s.size() - start));
    }
    else ans += stoi(s.substr(start, s.size() - start));
    cout << ans << '\n';
    return 0;
}