[백준 16637] 괄호 추가하기

문제링크 : https://www.acmicpc.net/problem/16637

C1) 한 자리의 양수만 계산
--> 처음 숫자의 음수여부는 고려하지 않아도 됨!! bb

C2) 괄호 안에는 하나의 연산자만 가능
--> 즉, 하나의 연산자에 괄호를 넣으면, 다른 연산자에는 괄호가 불가능!
--> "중복순열"을 이용해서 연산자에 괄호를 (사용할지, 말지)를 결정 (0 or 1)

💻 문제 풀이 : C++

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

#define ll long long
using namespace std;

int N;
// string input;
vector<int> num;
vector<char> oper;
vector<char> selected;
ll max_ans;

void CLEAR()
{
	N = 0;
	// input.clear();
	num.clear();
	oper.clear();
	selected.clear();
	max_ans = -2134567890;
}

void INPUT()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		char ch;
		cin >> ch;
		// input.push_back(ch);

		// #1. 한자리 양수만 다룸
		// => 짝수 idx : 수, 홀수 idx : 연산자
		if (i % 2 == 0)
			num.push_back((ch - '0'));
		else
			oper.push_back(ch);
	}
}

ll my_max(ll num1, ll num2)
{
	return num1 > num2 ? num1 : num2;
}

ll calc(ll num0, ll num1, char oper)
{
	if (oper == '+')
	{
		return num0 + num1;
	}
	else if (oper == '-')
	{
		return num0 - num1;
	}
	else if (oper == '*')
	{
		return num0 * num1;
	}
	else if (oper == '/')
	{
		// 조건에 없음.
	}
}

int is_rule_ok()
{
	for (int i = 0; i < selected.size() - 1; i++)
	{
		if (selected[i] == 1 && selected[i + 1] == 1)
			return 0;
	}
	return 1;
}

int get_new_calc()
{
	vector<int> temp_num=num;
	vector<char> temp_oper=oper;

	// 배열 삭제에 대한 flag
	int flag = 0;
	for (int i = 0; i < selected.size(); i++)
	{
		if (selected[i] == 1)
		{
			temp_num[i-flag] = calc(temp_num[i-flag], temp_num[i + 1 - flag], temp_oper[i - flag]);
			// num[i+1], oper[i] 삭제
			temp_num.erase(temp_num.begin() + (i + 1 - flag));
			temp_oper.erase(temp_oper.begin() + (i - flag));
			flag++;
		}
	}
	ll answer = temp_num[0];

	for (int i = 0; i < temp_oper.size(); i++)
	{
		answer = calc(answer, temp_num[i + 1], temp_oper[i]);
	}
	return answer;
}

// #?? 조합으로 이진을 어떻게 구현하는지
// => "중복순열"로... 사용할지말지 결정!!
void search(int depth)
{
	if (depth == N / 2) {
		// => 하나의 연산자에 추가했으면 주변 연산자는 불가능
		if (is_rule_ok()) {
			// 계산할 임시 배열 생성
			max_ans = my_max(get_new_calc(), max_ans);
		}
		return;
	}
	for (int i = 0; i <= 1 ; i++)
	{
		// => 연산자 마다 추가할지 말지를 결정...!
		selected.push_back(i);
		search(depth + 1);
		selected.pop_back();
	}
}

void SOLVE()
{
	search(0);
}

int main()
{
	CLEAR();
	INPUT();
	if (N == 1)
	{
		cout << num[0];
		return 0;
	}
	SOLVE();

	cout << max_ans;
	int dbg = 0;

	return 0;
}

📌 memo 😊
1. 0 or 1 과 같이 이진탐색을 할 때는 "중복순열"
https://velog.io/@rhkr9080/DFS-0-or-1-%EC%84%A0%ED%83%9D

2. vector에서 index를 제거하는 방법

v.erase(v.begin() + idx)

=> 제거할 때는 flag 를 이용해서 탐색할 idx도 같이 바꿔준다!!

3. N=1일때 Error 발생 ⚒
   => 경계값(최소)은 확인할 필요가 있음

4. Answer의 범위가 ~2^31 까지
   => 출력값의 범위가 longlong인지 확인해야함!