Life Engineering
[BOJ 16637] 괄호 추가하기 (C++) 본문
https://www.acmicpc.net/problem/16637
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int N;
string s;
vector<long long> operands;
vector<char> operators;
bool visit[19];
long long ans = (long long) -1 * pow(2, 31);
long long calc() {
long long answer;
vector<long long> num = operands;
vector<pair<char,bool> > op;
for (int i=0; i<operators.size(); i++){
op.push_back(make_pair(operators[i],visit[i]));
}
for (int i = 0; i < op.size(); i++) {
if (op[i].second) {
long long a = num[i];
long long b = num[i + 1];
switch (op[i].first) {
case '+':
num[i] = a + b;
break;
case '-':
num[i] = a - b;
break;
case '*':
num[i] = a * b;
break;
}
num.erase(num.begin() + i + 1);
op.erase(op.begin() + i);
i--;
}
}
answer = num[0];
for (int i = 0; i < op.size(); i++) {
switch (op[i].first) {
case '+':
answer += num[i + 1];
break;
case '-':
answer -= num[i + 1];
break;
case '*':
answer *= num[i + 1];
break;
}
}
return answer;
}
void backtracking(int cnt, int idx) {
if (cnt == operators.size()) {
ans = max(ans, calc());
return;
}
backtracking(cnt + 1, idx+1); //괄호 x
if (idx == 0 || !visit[idx-1]) { //괄호 o
visit[idx] = true;
backtracking(cnt + 1, idx+1);
visit[idx] = false;
}
}
int main() {
memset(visit, false, sizeof(visit));
cin >> N;
cin >> s;
for (int i = 0; i < N; i++) {
if (isdigit(s[i]))
operands.push_back((long long) s[i]-'0');
else
operators.push_back(s[i]);
}
backtracking(0,0);
cout << ans << "\n";
return 0;
}
괄호가 있는 경우=> 먼저 계산해주고, 해당 연산자와 피연산자를 erase 해준다. 괄호 안에 있는 연산자는 visit[i]=true로 표시를 해준다. 괄호가 있는 경우 다 계산된 것들을 좌측부터 순서대로 계산해주는 방식이다.
괄호가 있는 경우, 없는 경우 나뉘어서 DFS 탐색 해준다.
BUT 이렇게 복잡하게 안해줘도 된다.. 다른 분들의 코드를 참고해서 다시 해봤다.
#include <string>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int N;
string s;
long long ans=(long long) -1 * pow(2, 31);
long long calc(long long a, long long b, char op){
long long res;
switch(op){
case '+':
res=a+b;
break;
case '*':
res=a*b;
break;
case '-':
res=a-b;
break;
}
return res;
}
void dfs(int idx, long long result){
if (idx>=N){
ans=max(ans, result);
return;
}
char op=(idx==0)?'+':s[idx-1];
dfs(idx+2, calc(result, s[idx]-'0', op)); //괄호 포함x
if (idx+2<N){ //괄호 포함 o
long long bracket=calc(s[idx]-'0', s[idx+2]-'0', s[idx+1]);
dfs(idx+4, calc(result, bracket, op));
}
}
int main(){
cin>>N;
cin>>s;
dfs(0,0);
cout<<ans<<"\n";
return 0;
}
이전 값 , 현재 값을 연산하는 방식을 취한다. 현재 값의 인덱스=idx로, 괄호 추가 안할때는 이전 값과 현재값을 연산한다. 인덱스는 idx+2로 바꾸어준다.
괄호 추가 할 때는 이전 값과 (현재 값, 연산자, 다음 값) 을 연산해주고, 인덱스는 idx+4 로 바꾸어준다.
'Problem Solving' 카테고리의 다른 글
[BOJ 1197] 최소 스패닝 트리 (Python3) (0) | 2021.10.16 |
---|---|
[BOJ 17417] 게리맨더링 (C++) (0) | 2021.10.16 |
[BOJ 16235] 나무 재테크 (C++) (0) | 2021.10.12 |
[BOJ 10819] 차이를 최대로 (C++) (0) | 2021.10.12 |
[BOJ 9663] N-Queen (C++) (0) | 2021.10.12 |