[BOJ] 1541 잃어버린 괄호

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

1541번: 잃어버린 괄호

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

greedy

 

---------------------------------------------------풀이----------------------------------------------------

 

연산자가 +와 -뿐이므로, 식이 최소가 되는 경우는 뺄 값이 최대가 되도록 하는 것이다.

따라서, - 기준으로 묶어주는 방식을 취하면 된다.

즉, 123 + 234 - 345 + 456 + 567 - 678 + 789 라는 식이 주어진다면,

(123 + 234) - (345 + 456 + 567) - (678 + 789)

이런 식으로 괄호로 묶어 빼는 값이 최대가 되도록 만드는 것이다.

 

이를 위해 식을 숫자와 연산자로 나누어 주고,

find_min()함수에서 큐를 사용해

+가 나오면 queue의 front에 더해주고,

-가 나오면 queue에 삽입하는 방식으로 구현하였다.

최종적으로 queue에는 괄호 안의 값들이 계산되어 들어있을 것이므로,

front에서 시작해 각 값을 빼면 정답을 구할 수 있다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

vector<int> nums;
vector<char> ops;

int find_min(){
    // 덧셈끼리 전부 묶어서 빼는 값이 커지도록 만들기
    queue<int> s;
    s.push(nums[0]);
    int nums_idx = 1;
    for(int i = 0; i < ops.size(); i++){
        if(ops[i] == '+'){
            s.back() += nums[nums_idx];
        }
        else{
            s.push(nums[nums_idx]);
        }
        nums_idx++;
    }
    int ans = s.front();
    s.pop();
    while(!s.empty()){
        ans -= s.front();
        s.pop();
    }
    return ans;
}

// 괄호를 적절히 쳐서 이 식의 값을 최소로 만들어라.
int main(void){
    FASTIO;
    string str;
    cin >> str;
    int num = 0;
    for(int i = 0; i < str.length(); i++){
        if(str[i] == '+' || str[i] == '-'){
            nums.push_back(num);
            num = 0;
            ops.push_back(str[i]);
        }
        else{
            num = num * 10 + str[i]-'0';
        }
    }
    nums.push_back(num);

    cout << find_min() << "\n";
    
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

처음엔 브루트포스로 모든 케이스를 찾으려 했으나, +와 -뿐인 operator를 보고 방식을 수정했다.

뺄 수 있는 값이 최대가 되도록 하면 되는 간단한 문제였다.