백준 1541번: 잃어버린 괄호 (그리드 알고리즘)

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

1541번: 잃어버린 괄호

문제

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

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

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

입력

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

출력

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

 

이 문제 또한 최선의 수를 찾아 가는 과정이다. 여기서 최선의 최솟값은 -부호가 나온순간 뒤에 +부호는 다 괄호로 묶어서 -로 만들어 버리는 것이다.

예를 들면 1+2+3-4+5+6+7-8+8일 경우

- 부호 뒤에를 괄호로 묶어 버려서 뺴주는 것이 최선이다

즉 1+2+3-(4+5+6+7)-(8+8) 이다.

코드를 보자

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
    string s;
    cin>>s;
    vector<int> num;           // 숫자 저장
    vector<char> sign;        //부호 저장
    int number=0;
    sign.push_back(1);
    for(int i=0;i<s.size();i++){
        if(s[i]=='-' || s[i]=='+'){       //부호일경우 저장
            if(s[i]=='-'){
                sign.push_back(-1);
            }
            if(s[i]=='+'){
                sign.push_back(1);
            }
            num.push_back(number);
            number=0;
        }
        else{
            number=number*10+(s[i]-'0');       //문자열을 숫자로 치환
        }
    }
    num.push_back(number);
    bool minus=false;
    int sum=0;
    for(int i=0;i<num.size();i++){
        if(sign[i]==-1){          //-가 나오면 쭉 뺴면 됨 그 이유는 어차피 괄호로 묶어서 다 뺴기 떄문
            minus=true;
        }
        if(minus==false){
            sum+=num[i];
        }
        if(minus==true){
            sum-=num[i];
        }
    }
    cout<<sum;

}