[BOJ 16637] 괄호 추가하기 (C++)

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

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 로 바꾸어준다.