BOJ - 1541 - 잃어버린 괄호
문제
문제 개념
문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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;
}
SOL
- ( + )인 경우들을 먼저 묶어 계산 후 ( - )를 처리한다.