백준_1541 : 잃어버린 괄호 - C++

문제

---

문제 해석

- 주어진 식에 괄호를 잘 쳐서 식의 결과가 최소가 되도록 하면 되는 문제이다.

- 이때의 결과값을 출력 하면 된다.

---

알고리즘

- 식이 최소가 되기 위해선 빼기 연산을 최대한 많이 해 주는 것이 좋다.

  - 예를 들어 "55-50+40+30" 이라면 -50만 빼주는 것 보단 "55 - (50+40+30)" 을 해 주는 것이 더 최소라는 말이다.

- 빼기 연산을 가장 크게 해 주기 위해서는 식에서 처음 나오는 "-" 부호 뒤의 숫자는 모두 빼 주면 된다.

- 다음과 같은 식 처럼 - 부호 가 하나라도 나오게 되면 그 뒤 숫자들은 모두 빼기 연산으로 수행 되도록 묶을 수 있기 때문이다.

- 따라서 문제를 풀기 위해선 처음 나오는 - 부호까지는 모두 더해 주고 - 부호 이후에 나오는 숫자들은 모두 빼 주면 된다.

---

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string input, front, back;
int ans = 0;

int main(){
    cin >> input;
    char op = '+';
    for(int i = 0; i < input.length(); i++){
        if(input[i] == '-' || i == input.length()-1){
            front = input.substr(0, i+1);
            back = input.substr(i+1, input.length()-i);
            break;
        }
    }

    int start = 0;
    for(int i = 0; i < front.length(); i++){
        if(front[i] == '+' || i == front.length()-1){
            string tmp = front.substr(start, i-start+1);
            ans += stoi(tmp);
            start = i+1;
        }
    }
    start = 0;
    for(int i = 0; i < back.length(); i++){
        if(back[i] == '+' || back[i] == '-' || i == back.length()-1){
            string tmp = back.substr(start, i-start+1);
            ans -= stoi(tmp);
            start = i+1;
        }
    }
    cout << ans << '\n';
}