1. 풀이

우선 완전 탐색이라는 것은 대충 감이 왔을 것이다.

완전 탐색을 어떻게 구현할지가 문제이다.

• 법칙 1 : 완전 탐색은 항상 앞에서 뒤로간다. (인덱스 0에서부터 --> 방향으로만 진행한다는 의미)

• 법칙 2 : 인덱스 0에서부터 --> 방향으로만 진행하며, 각 인덱스에서 선택할 수 있는 경우의 수를 생각해보자
  

-> 이 문제의 경우 각 인덱스에서 선택할 수 있는 경우의 수는 오직 2개이다.

경우의 수가 2개니까 -> go() 재귀 호출을 2번 수행하도록 코드짜면 된다.

• 법칙 3 : 인덱스 idx를 활용해서 로직을 설계한다.

경우 1은 idx와 idx+1의 연산이고, 경우 2는 idx+1 과 idx+2의 연산 후에 idx와 연산을 수행한다.

또한 구간합의 개념이 들어가야한다. 기본은 앞에서부터 구간합이고, 괄호를 만난 경우만 뒤에꺼 연산하고 구간합과 연산한다고 생각하면된다.

2. 코드

#include <bits/stdc++.h>

using namespace std;



int ret = -987654321;
vector<int> num;
vector<char> operand;

int calc(int num1, char op, int num2) {
	switch(op) {
		case '+' : return num1+num2;
		case '*' : return num1*num2;
		default : return num1-num2;
	}
}

void go(int idx, int psum) {
	if(idx == num.size()-1) {
		ret = max(ret, psum);
		return;
	}
	go(idx+1, calc(psum, operand[idx], num[idx+1]));
	if(idx+2 <= num.size()-1 && idx+1 <= operand.size()-1) {
		int tmp = calc(num[idx+1], operand[idx+1], num[idx+2]);
		go(idx+2, calc(psum, operand[idx], tmp));
	}	
}



int main() {
	int n;
	string s;
	cin >> n;
	cin >> s;
	for(int i=0;i<n;i++) {
		if(i%2==0) {
			num.push_back(s[i]-'0');
		} else operand.push_back(s[i]);
	}
	
	go(0,num[0]);
	cout << ret;

	return 0;
} 

3. 오답노트

(1) 완탐 재귀함수 go() 미숙 (중요)

완탐 재귀 함수 go() 구현이 미숙하다. 처음에 완탐을 해야함과 go() 재귀함수를 만들어야함은 캐치했다.
그러나 각 idx에서 어떤 경우의 수가 있는지, 어떻게 구현할지가 떠오르지 않았다.

재귀 구조를 잘 이해하고있어야겠다.

• 완탐은 항상 앞에서 뒤로간다
• 앞에서부터 시뮬레이션 돌리면서 각 idx에서 분기되는 경우의 수를 살펴보자
• idx를 활용해서 코드를짠다

위의 3가지를 잊지말자.