구현 문제이다. 처음에는 괄호라는 키워드가 나오자 자료 구조를 이용해서 해결하는 문제인가? 싶었지만 괄호의 갯수가 정해져 있지 않고 사용 할 수 있는 갯수를 알려주지 않는 것이다. 그래서 괄호를 사용할 수 있는 갯수까지 확인하는 완전 탐색 문제라고 생각해 풀이하게 되었다.

그리고 주어진 n마다 사용 할 수 있는 괄호의 최대 갯수는 정해져 있다고 생각했기 때문에 n의 범위도 작으니 미리 최대 괄호의 갯수를 정하고 풀이를 이어나갔지만 결국 해결하지 못했다.

괄호의 최대 갯수가 정해져 있더라도 그 괄호를 사용할건지 어느 위치에 사용 할 것인지 너무 많은 조건 사항이 있었기 때문이다.

문제의 주요 포인트는 2가지 였다.

1. 괄호를 넣을 수 있는 모든 경우의 수를 검사할 것
2. 답은 음수 최소 값 ~ 양수 최대 값 까지 가능하다.

1번은 아래 정답 풀이와 같이 로직을 어느정도 이해하니 해결 할 수 있었는데 2번을 알아차리지 못해 반례 게시판을 찾아보았다. 문제상에서 출력답을

위와 같이 -2의 31승까지 가능하였기에 만약 result의 초기값을 0으로 하고 단순하게 max나 비교연산을 사용했더라면 정답 처리 될 수 없었다.

오답

#include <iostream>
#include <vector>
#include <cstring>

char v[20];

using namespace std;
bool check[20];
int n;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		v[i] = s[i];
	}

	//3보다 적으면 그냥 처음꺼 출력해주면 됨
	if (n < 3) {
		cout << v[0] - '0';
		return 0;
	}
	int count = 1;

	if (n == 3 || n==5) count = 1;
	if (n == 7 || n == 9) count = 2;
	if (n == 11 || n == 13) count = 3;
	if (n == 15 || n == 17) count = 4;
	if (n == 19) count = 5;

	int cur = v[0] - '0';
	int result = 0;

	//괄호를 0개부터 count개까지 사용해서 최대값 찾음
	for (int c = 0; c <= count; c++) { 
		//z개부터 c개 까지의 괄호를 배치 괄호는 짝수칸에만 놓을 수 있음
		for (int z = 0; z < c; z++) {
			//짝수칸 순회 
			for (int x = 2; x < n; x++) {
				if (x % 2 == 1) continue;
			}
		}
	}

	for (int i = 1; i < n; i++) {
		//칸이 연산 기호일 경우
		if (v[i] == '+') {
			result += (v[i + 1] - '0');
			i++;
		}
		else if (v[i] == '-') {
			result -= (v[i + 1] - '0');
			i++;
		}
		else if (v[i] == '*') {
			result *= (v[i + 1] - '0');
			i++;
		}

	}

	result = max(cur, result);

	cout << result;

	return 0;
}

정답 출처

#include <iostream>
#include <vector>
#include <cstring>

char v[20];


int cur = 0;
using namespace std;
int result = -999999999;

string s;
int n;

void dfs(int cur , int tmp) {

	//연산 범위가 n을 넘고 연산한 결과인 tmp가 result를 넘었을 경우 return
	if (cur > n && tmp > result) {
		result = tmp;
		return;
	}

	//괄호 연산 할 수 있음
	if (cur + 2 < n) {
		//현재 숫자 위치 기준으로 앞의 숫자와 연산을 한 다음에 이전 값을 더한 다음에 다음 연산에 더해줘야함. 그런데 현재 위치가 0이라면 이전 값이 없기 때문에 바로 넣어준다.
		//char 형태이기 때문에 int 형변환을 위해 - '0'
		int cur1 = (s[cur] - '0');
		int cur2 = (s[cur + 2] - '0');
		int cur_tmp = 0;
		if (s[cur + 1] == '+') {
			cur_tmp = cur1 + cur2;
		}
		else if (s[cur + 1] == '-') {
			cur_tmp = cur1 - cur2;
		}
		else if (s[cur + 1] == '*') {
			cur_tmp = cur1 * cur2;
		}
		//또 괄호 연산이 가능하다고 가정으로 넘기는 것임
		if (cur == 0) {
			dfs(cur + 4, cur_tmp);
		}
		else {
			if (s[cur - 1] == '+') {
				cur_tmp = cur_tmp + tmp;
			}
			else if (s[cur - 1] == '-') {
				cur_tmp = tmp - cur_tmp;
			}
			else if (s[cur - 1] == '*') {
				cur_tmp = cur_tmp * tmp;
			}
			dfs(cur + 4, cur_tmp);
		}
	}
	//괄호 연산을 하지 않는 경우
	if (cur == 0) {
		dfs(cur + 2, s[cur] - '0');
	}
	else {
		if (s[cur - 1] == '+') {
			dfs(cur + 2, (s[cur] - '0') + tmp);
		}
		else if (s[cur - 1] == '-') {
			dfs(cur + 2, tmp - (s[cur] - '0'));
		}
		else if(s[cur - 1] == '*') {
			dfs(cur + 2, (s[cur] - '0') * tmp);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	cin >> s;

	dfs(0, 0);

	cout << result;

	return 0;
}