cpp) 백준 1541: 잃어버린 괄호

Problem

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

1541번: 잃어버린 괄호

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
 
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
 
 

Solution

#include<iostream>
#include<string>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    
    string s;
    cin >> s;

    int result = 0;
    string num;
    bool isMinus = false;

    for(int i=0;i<=s.size();i++){
        if (s[i]=='-' || s[i]=='+' || i==s.size()){
            // 1. 숫자가 아닌 경우
            if(isMinus) {
                // 2. '-' 연산자가 나온 경우 수들을 빼줌
                result -= stoi(num);
                num = ""; 
            } else {
                // 2. '-' 연산자가 아닌 경우 수들을 더해줌
                result += stoi(num);
                num="";
            }

        } else {
            num += s[i];  // 1. 숫자인 경우 
        }

        if (s[i]=='-')
            isMinus = true;
    }

    cout << result << '\n';

   return 0;
}

 
55 - 50 + 40 + 30 - 20 + 10 의 경우, 해당 값의 최소는 55 - (50 + 40 + 30) - (20 + 10) = -95 이다. '-' 부호가 앞에 존재할 때, 뒤의 값들을 모두 빼줌으로써 최솟값을 구할 수 있다. 
 
 

Reference

https://beginnerdeveloper-lit.tistory.com/116

[C++] 백준 1541번 잃어버린 괄호