BOJ 1541 - 잃어버린 괄호

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

'+'와 '-'와 숫자로만 이루어진 수식이 주어진다.

이때 임의의 위치에 괄호를 넣을수 있을때, 가장 최솟값을 구하시오.

Solution

문제에서 주어진 예제를 보자.

Input

55-50+40

Output

-35

결과값만 본다면 55 - 50 - 40 과 일치하다.

-> 55 - (50+40)

'-' 연산자가 나오게 된다면 그 이후의 모든값은 뺄셈이 가능하다는 뜻이다.

또 다른 예제를 들어보면,

Input

100 + 30 - 10 + 40 - 20 + 50

Output

10

-> 100 + 30 - (10+40) - (20+50)

위와 같이 '-'가 한번이라도 나오게 된다면 그 이후의 '+' 연산들은 모두 괄호로 묶어서 뺄셈이 가능하고, '-' 부호는 그대로 뺄셈을 진행하면 된다.

Code

숫자를 넣을 배열과 연산자(부호)를 저장할 배열을 준비한후에 반복문을 돌리다가 '-' 부호가 나오게 되면 그 이후의 모든 숫자들은 빼주면 된다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<int> num;
    vector<char> sign;
    bool state = false;
    int ans = 0;
    int temp = 0;
    string str;

    cin >> str;

    sign.push_back('+'); //처음 숫자 앞에는 + 연산자가 사실상 붙어있는것

    for (int i = 0; i < str.size(); i++) {

        if (str[i] == '+' || str[i] == '-') {
            if (str[i] == '+') {
                sign.push_back('+');
            }
            else {
                sign.push_back('-');
            }

            num.push_back(temp); //연산자가 나왔다는건 앞의 숫자계산이 다 되었다는 뜻
            temp = 0;
        }

        // 숫자라면 숫자의 값을 계산해줌. 
        else {
            temp = temp * 10 + str[i] - '0';
        }
    }
    num.push_back(temp); //마지막 숫자 넣어줌 (끝에는 연산자가 없기에)
 
    for (int i = 0; i < num.size(); i++) {
        if (sign[i] == '-') {
            state = true;
        }

        if (state) {
            ans -= num[i];
        }
        else {
            ans += num[i];
        }
    
    }

    cout << ans << '\n';

    return 0;
}

참고 : https://code.plus/course/43 , 그리디 알고리즘(연습)