BOJ - 1541 - 잃어버린 괄호

ggh·2022년 6월 10일

boj cpp greedy ps

백준

목록 보기

41/112

BOJ - 1541 - 잃어버린 괄호

문제

1541번: 잃어버린 괄호

문제 개념

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

구현

#include <iostream>
#include <vector>

using namespace std;

// 주어진 식에서 괄호를 치는 행위를 통해 최솟값을 구하여라 
// 1. 순서는 바뀔 수 없으며 오로지 괄호를 이용한다. 
// 2. (-)가 존재하면 (+)끼리 묶어 먼저 계산한다. 

int main()
{
    // 식 입력 받기 
    string str;
    cin >> str;
    vector<int> iv;
    vector<char> ic;
    string temp = "";
    for(int i=0; i <= str.size(); i++)
    {

        if(str[i] == '-' || str[i] == '+' || i == str.size())
        {
            iv.push_back(stoi(temp));
            temp = "";
            ic.push_back(str[i]);
            
        }
        else
            temp += str[i];
    }
    // 양의 부호를 가지면 묶는다. 
    for(int i=0; i < ic.size(); i++)
    {
        if(ic[i] == '+')
        {
            iv[i] += iv[i+1];
            iv.erase(iv.begin() + i+1);
            ic.erase(ic.begin() + i);
            i--;
        }
    }
    // 이후 음의 부호를 가지는 것들을 해결한다.
    for(int i=0; i < ic.size(); i++)
    {
        if(ic[i] == '-')
        {
            iv[i] -= iv[i+1];
            iv.erase(iv.begin() + i+1);
            ic.erase(ic.begin() + i);
            i--;
        }
    }
    int answer = iv[0];
    cout << answer << endl;
    return 0;
}