[BOJ] 16638. 괄호 추가하기2

*괄호 추가하기1에서 연산자 우선순위만 추가 (계산 단계 하나만 추가됐다)

*숫자 자리수를 계산하기 번거로와서 string으로 처리함 

2019/10/08 - [BOJ/C++] - [BOJ] 괄호추가하기

[BOJ] 괄호추가하기

*단계

1) 괄호 추가 (addd)

- added[i] = true 인 부분은 괄호에 속하는 숫자들이다. 

- 괄호 안에 연산자는 하나만 들어갈 수 있기 때문에 연산자를 기준으로 i와 i+2를 검사한다. 

 

2) added[i] == false라면 괄호 안에 있는 숫자 혹은 연산자가 아니기 때문에 후에 계산을 진행해야 한다. 

res 라는 string 백터에 넣는다. 

added[i] == true라면 계산을 진행한 후 결과값을 res에 넣는다. 

 

3) 이 단계가 왔다면 res에는 

(3+8) * (7-9) * 2  =>res = [ 11, *, -2, *, 2] 이 저장되어있을 것이다. 

 

연산자 우선순위에 따라서 *는 먼저 계산이 되어야 한다. 

스택의 특성을 이용해서 '*' 연산자가 나오면 가장 위에 있는 숫자와 계산한 값을 넣어주고, 숫자 혹은 '+', '-' 라면 바로 넣어준다. 

 

4) 마지막으로 스택에 남은 숫자들을 연산자에 따라 저장 

 

5) 다시 addd() 로 되돌아와서 최대값 계산 

 

 

#include <iostream> #include <vector> #include <stack> #include <string> #define INF -987654321 using namespace std; int n, ans = INF; char expr[21]; bool added[21]; int go(int f, int s, char op) { switch (op) { case '+': return f + s; case '-': return f - s; case '*': return f * s; } } int calc() { vector<string> res; //계산할 숫자와 부호를 저장 //우선순위-> 괄호 -> 연산자 우선순위에 따라 for (int i = 0; i < n;) { if (!added[i]) { string x(1, expr[i]); res.push_back(x); i++; } else { //계산해서 넣는다. int t1 = expr[i] - '0'; int t2 = expr[i + 2] - '0'; int tres = go(t1, t2, expr[i + 1]); res.push_back(to_string(tres)); i += 3; } } vector<string> st; for (int i = 0; i < res.size(); i++) { if (res[i] == "*") { int t1 = stoi(st.back()); st.pop_back(); int t2 = stoi(res[i + 1]); int tres = t1 * t2; st.push_back(to_string(tres)); i++; } else { st.push_back(res[i]); } } int sum = stoi(st[0]); for (int i = 1; i < st.size(); i += 2) { if (st[i] == "+") { sum += stoi(st[i + 1]); } else if (st[i] == "-") { sum -= stoi(st[i + 1]); } } return sum; } void addd(int idx) { if (idx >= n) { int res = calc(); ans = ans > res ? ans : res; return; } for (int i = idx; i < n; i += 2) { if (i + 2 < n) { if (!added[i] && !added[i + 2]) { //연산자를 하나만 포함해야한다. added[i] = added[i + 2] = true; addd(i + 2); added[i] = added[i + 2] = false; } } else { addd(i + 1); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n; i++) { cin >> expr[i]; } addd(0); cout << ans << '\n'; return 0; }