[BOJ - 16637] 괄호 추가하기

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

16637번: 괄호 추가하기

 

 

이런 류의 문제를 처음 접해보면 어렵게 느껴질수도 있다.

 

이런 류의 문제를 프로그래머스에서 스타트업 인턴을 모집하는 코딩테스트였나.. 우아한테크코스 코딩테스트였나.. 라인 인턴 코딩테스트였나...

 

아무튼 어떤 코딩테스트에서 본 적이 있다.(하지만 그 때 문제는 경우의 수가 좀 많아서 시간 초과가 날 수도 있었다)

 

이 문제를 풀 때 포인트는 실제로 괄호를 추가하면 문자열 파싱하느라 시간만 잡아먹으니 그냥 괄호 역할을 대신해줄 표시(?)를 해주면 된다.

 

내가 작성한 코드를 봤을때 전역변수로 선언한 separate[21] 이라는 배열을 주목하면 된다.

 

- 풀이 방법

1. 입력을 받는다.

 

2. dfs + 백트래킹으로 풀 생각을 한다.

(괄호를 추가해주는 모든 경우의 수에 대해 완탐을 해보기 위해)

 

3. dfs로 방문할 때마다 최댓값을 갱신해준다.

 

4. 최댓값을 갱신한 후 괄호를 표시해준다.

(separate라는 배열의 i번째와 i+2번째를 표시해주면 된다. 3개씩 묶어서 먼저 계산해준다고 생각하면 편함)

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int n, res;
char str[21];
int separate[21];

int calc() {
	vector<string> temp;

	int i = 0;

	while (i < n) {

		if (separate[i] == 0) {
			string s = "";
			s = str[i];
			
			temp.push_back(s);
			i += 1;
		}

		else {
			if (str[i + 1] == '+') {
				temp.push_back(to_string((str[i] - '0') + (str[i + 2] - '0')));
			}

			else if (str[i + 1] == '-') {
				temp.push_back(to_string((str[i] - '0') - (str[i + 2] - '0')));
			}

			else if (str[i + 1] == '*') {
				temp.push_back(to_string((str[i] - '0') * (str[i + 2] - '0')));
			}

			i += 3;
		}
	}

	int func_res = stoi(temp[0]);

	for (int i = 1; i < temp.size(); i++) {
		
		if (temp[i] == "+") {
			func_res += stoi(temp[i + 1]);
			i += 1;
		}
		else if (temp[i] == "-") {
			func_res -= stoi(temp[i + 1]);
			i += 1;
		}
		else if (temp[i] == "*") {
			func_res *= stoi(temp[i + 1]);
			i += 1;
		}
	}

	return func_res;
}

void dfs(int node) {

	res = max(res, calc());

	for (int i = node; i + 2 < n; i += 2) {
		if (separate[i] == 0 && separate[i + 2] == 0) {
			separate[i] = 1, separate[i + 2] = 1;
			dfs(node + 2);
			separate[i] = 0, separate[i + 2] = 0;
		}
	}
}

int main(void) {

	scanf("%d", &n);
	scanf("%s", str);

	res = -0x7fffffff;

	dfs(0);

	printf("%d\n", res);

	getchar();
	getchar();

	return 0;
}