BOJ 1541번 : 잃어버린 괄호

문제를 읽어보면 알겠지만 논리적으로는 굉장히 쉬운 문제이다.

다만 입력을 문자열로 받기에 그 부분을 처리하는데 있어 조금 귀찮을 뿐이다.

 

<Solution>

 

예를들어 55-50+40 이 주어질 경우, 가장 작은 값을 만들기 위한 괄호는 55-(50+40) 이다.

 

즉, 55-50-40 으로 만들면 된다는 것이다.

 

이를 위해 음수 이후의 덧셈을 모두 뺄셈 처리를 해주면 해결된다.

 

위 처럼 계산을 해주기 위해 문자열을 적절히 처리하여 배열에 {55, -50, 40} 으로 넣어주었다.

 

위 배열처럼 만들기 위해 아스키 코드 값을 기준으로 숫자를 분류하였고, atoi() 를 사용하여 정수값으로 변환 시켰다.

 

<소스코드>

#include<iostream>
#include<string>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
 
void Solve(string s) {
    int res = 0;
    vector<int> v;
    string tem = "";
 
    for (int i = 0; i < s.length(); i++) { // 나눠서 배열에 넣음
 
        if (s[i] == '-' || s[i] == '+') { // 문자일때
            v.push_back(atoi(tem.c_str()));
            tem = "";
            tem = tem + s[i];
        }
        else if (s[i] <= 57 && s[i] >= 48) // 숫자일때
            tem = tem + s[i];
 
        if (i == s.length() - 1)           // 마지막은 문자이므로
            v.push_back(atoi(tem.c_str()));
    }
 
    res = v[0];
    bool flag = false;
 
    for (int i = 1; i < v.size(); i++) {
 
        if (v[i] < 0) { // 음수 나오면 뒤에 더하기 다 음수처리 하기위한 플래그 설정
            res += v[i];
            flag = true;
        }
        else if (flag)  // 앞에 음수였으면 더하기 다 빼버림
            res -= v[i];
        
        else           // 나머진 더함
            res += v[i];
 
    }
    cout << res;
 
}
 
int main() {
 
    string s;
    cin >> s;
 
    Solve(s);
}

 

<문제>

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호