1541번

1541번 - 잃어버린 괄호

처음에 완전탐색을 할까 했지만, 생각보다 복잡할 것 같았다.

그런데 그리디적인 방법으로 생각해보면,

- + + + - + + - + + 이 나오면 괄호를 씌워, 전부다 - 로 바꿀 수 있다.

즉 - ( + + + ) - (+ +) - (+ +) 이런식으로 전부 -로 바꾸면 최소값을 구할 수 있기 때문이다.

따라서 처음에만 +를 해주고, - 가 나온 이후로는 그냥 빼주기만 하면 된다.

<정답 코드>

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
int main()
{
    string str;
    int cnt = 0;
    cin >> str;
 
    int sum = 0;
    string num = "";
    char cur = '+';
 
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] >= '0' && str[i] <= '9')
        {
            num += str[i];
        }
 
        if (str[i] == '-' || str[i]=='+' || i==str.size()-1)
        {
            if (cur == '+')
            {
                sum += stoi(num);
            }
            else if (cur == '-')
            {
                sum -= stoi(num);
            }
 
            if (str[i] == '-')
            {
                cur = '-';
            }
 
            num = "";
        }
    }
 
    cout<<sum<<"\n";
 
    
    
 
     return 0;
}