백준 1541 (잃어버린 괄호) c++

문제

1541번: 잃어버린 괄호

숫자와 연산자가 포함된 식이 주어지면 임의의 괄호를 쳐서 가장 작은수를 출력하면 됩니다.

예를 들어 55 - 50 + 40 이라는 식이 주어지면 55 -(50 + 40) = -35 이렇게 최소의 값을 출력하게 하면 됩니다.

 

처음에는 괄호를 처음부터 치면서 brute force문제 인지 알았지만 brute force로 구현이 어려워

힌트를 찾아봤습니다.

 

100 - 10 + 50 -10 + 100

다음과 같은 식을 최소로 만들려면

100 -(10 + 50) -(10 + 100) = -70 이됩니다.

 

100 - 10 + 50  + 10 + 100

다음과 같은 식을 최소로 만들려면

100 -(10 + 50 + 10 + 100) = -70이 됩니다.

 

즉, 식에서 '-' 가 나오게 되면 그 뒤에 식이 어떤것인지 상관없이 괄호로 묶어주면 됩니다.

 

문제에서 문자열로 이루어진 식이 입력으로 주어지므로 

이를 주의해서 파싱해 쪼개주어야 합니다.

vector<int>arr;
vector<char>ch;
string st;
cin >> st;
 
int ans = 0;
for (int i = 0; i < st.size(); i++) {
    if (st[i] >= '0' && st[i] <= '9') {
        if (ans) {
            ans *= 10;
            ans += st[i] - '0';
        }
        else ans += st[i] - '0';
    }
    else {
        arr.push_back(ans);
        ans = 0;
        ch.push_back(st[i]);
    }
    if (i == st.size() - 1) {
        arr.push_back(ans);
    }
}

숫자는 arr 벡터에 넣어주고 연산자는 ch벡터에 넣어줍니다.

int answer = 0;
bool minus = false;
int ex = 0;
for (int i = 0; i < arr.size(); i++) {
    if (minus) {
        ex += arr[i];
    }
    else answer += arr[i];
 
    if (i == arr.size() - 1)
        continue;
    if (ch[i] == '-') {
        minus = true;
    }
}
cout << answer + ex * -1;

이제 식을 돌아보면서 '-' 가 나오면 bool 형인 minus가 true가 되면서 모두 ex라는 변수에 누적합으로 저장되

마지막에 -1을 곱해 계산해 주면 됩니다. answer형에는 '-'가 나오기 전까지의 누적합이 들어갑니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
vector<int>arr;
vector<char>ch;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    string st;
    cin >> st;
 
    int ans = 0;
    for (int i = 0; i < st.size(); i++) {
        if (st[i] >= '0' && st[i] <= '9') {
            if (ans) {
                ans *= 10;
                ans += st[i] - '0';
            }
            else ans += st[i] - '0';
        }
        else {
            arr.push_back(ans);
            ans = 0;
            ch.push_back(st[i]);
        }
        if (i == st.size() - 1) {
            arr.push_back(ans);
        }
    }
    int answer = 0;
    bool minus = false;
    int ex = 0;
    for (int i = 0; i < arr.size(); i++) {
        if (minus) {
            ex += arr[i];
        }
        else answer += arr[i];
 
        if (i == arr.size() - 1)
            continue;
        if (ch[i] == '-') {
            minus = true;
        }
    }
    cout << answer + ex * -1;
    
 
 
    return 0;
}