BOJ - 1541 잃어버린 괄호

+와 -로 구성된 수식에서 괄호를 적절히 묶어 식의 결과가 최소가 되도록 하는 문제이다.

문제풀이 전략
연산 결과가 최소가 되기 위해서는 -를 최대로 해 주면 된다.

처음 접근은 다음과 같이 하였다.

수식을 순회하다가 -가 나오면 다음 -가 나오기 전까지 다 더해서 빼주는 방식을 사용하였다. (코드의 주석부분)

그러나 생각해 보니 처음 -가 나온 이후의 수들을 모두 빼주면 되는 것이었다.

예를들어 1+2+3-4-5+6-7이 있다고 치면
1+2+3-(4)-(5+6)-(7) 이 되므로 그냥 첫 - 이후의 값들을 부호 상관없이 모두 빼주면 되는 것이다.

코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;
int main() {
    string str = "";
    cin >> str;
    vector<int> num;
    vector<char> op;
    string tmp = "";
    for(int i=0;i<str.size();i++){
        if(str[i] == '+' || str[i] == '-'){
            op.push_back(str[i]);
            num.push_back(stoi(tmp));
            tmp = "";
        }else{
            tmp += str[i];
        }
    }
    num.push_back(stoi(tmp));

    int ans = num[0];
    int flag = 0;
    for(int i=0;i<op.size();i++){
        if(op[i] == '-'){
            flag = 1;
        }
        if(flag == 1){
            ans -= num[i+1];
        }else{
            ans += num[i+1];
        }
    }
    cout << ans << "\n";

//    int ans = num[0];
//    for(int i=0;i<op.size();i++){
//        if(op[i] == '-'){
//            int a = num[i+1];
//            while(op[i+1] == '+') {
//                i++;
//                a += num[i+1];
//            }
//            ans -= a;
//        }else{
//            ans += num[i+1];
//        }
//    }
//    cout << ans << "\n";

    return 0;
}

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