글 읽기 - [틀렸습니다] 질문있습니다!!!

wony6731 4년 전 0

질문게시판에 나와있는 반례를 모두 해보았으나 제 코드가 왜 틀린지 잘 모르겠습니다...

제가 접근한 방법은 이러합니다.

먼저 연산자와 피연산자를 각각 벡터로 받은 다음, 놓을 수 있는 괄호의 모든 경우에 대해 완전탐색을 진행합니다.

저는 괄호의 표시를 괄호 안에 연산자가 하나만 존재하기 때문에 연산자에게 우선순위를 표시하여 먼저 계산되도록

하였습니다. 그리하여 Calculate 함수 안에 있는 V1, V2는 우선순위가 높은(괄호안에 있는) 연산자를 먼저 계산하여 업데이트하게 됩니다.

1%도 뜨지 않고 바로 틀렸습니다 라고 뜹니다... 어디 놓친 부분이 있는 것 같은데 혹시 어느 부분이 문제인지 반례라도 알 수 있을까요....? ㅜㅜ

/*
	Title : 괄호 추가하기
	Description
		- 길이기 N인 수식
		- 수식 : 0~9, +, -, x	(우선순위 동일)
		- 괄호 안에 연산자는 하나만 있어야 함, 중첩 괄호 사용 불가
		- 식의 결과 최댓값은?
	Solution
		- 가능한 괄호의 갯수 "0 ~ par_cnt"에 대하여 완전 탐색
*/
/*
N=1		->	0
N=3		->	1
N=5		->	1
N=7		->	2
N=9		->	2
N=11	->	3
N=13	->	3
N=15	->	4
N=17	->	4
N=19	->	5
...
0 1 2 3 4 5 6
*/
#include <iostream>
#include <vector>

using namespace std;

int N, par_cnt;
int arr[19];
bool isused[19];
vector<int> operands;
vector<char> operators;
int max_answer = 0;

void SelectOperators(int k, int total);
void Calculate(int total);

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	int a = (N - 1) / 2;
	par_cnt = (a + 1) / 2;

	for (int i = 0; i < N; i++){
		if (i % 2 == 0){
			int tmp;
			cin >> tmp;
			operands.push_back(tmp);
		}
		else {
			char tmp;
			cin >> tmp;
			operators.push_back(tmp);
		}
	}

	// 괄호 갯수에 맞춰 탐색
	for (int i = 0; i <= par_cnt; i++){
		//cout << "괄호 " << i << "개 선택\n";
		SelectOperators(0, i);
	}

	cout << max_answer << "\n";
	

	return 0;
}

// 괄호 선정하기(연산자에 우선순위 부여하기)
// arr 배열에 우선순위가 부여된 연산자의 인덱스 저장
void SelectOperators(int k, int total){
	if (k == total){
		// Test code
		/*for (int i = 0; i < k; i++)
			cout << operators[arr[i]] << " ";
		cout << "\n";*/

		// 값 계산
		Calculate(total);

		return;
	}

	for (int i = 0; i < operators.size(); i++){
		if (isused[i]) continue;

		if (k == 0){
			arr[k] = i;
			isused[i] = true;
			SelectOperators(k + 1, total);
			isused[i] = false;
		}
		else{
			if (arr[k - 1] + 1 < i){
				arr[k] = i;
				isused[i] = true;
				SelectOperators(k + 1, total);
				isused[i] = false;
			}
		}
	}
}

void Calculate(int total){
	int cal_value = 0;
	int operators_idx = 0;
	vector<int> V1 = operands;
	vector<char> V2 = operators;

	// 우선순위 먼저 계산
	int del_cnt = 0;
	for (int i = 0; i < total; i++){
		operators_idx = arr[i] - del_cnt;
		int operands_idx_left = operators_idx;
		int operands_idx_right = operators_idx + 1;

		switch (V2[operators_idx]){
		case '+':
			cal_value = V1[operands_idx_left] + V1[operands_idx_right];
			break;
		case '-':
			cal_value = V1[operands_idx_left] - V1[operands_idx_right];
			break;
		case '*':
			cal_value = V1[operands_idx_left] * V1[operands_idx_right];
			break;
		default:
			cout << "error1\n";
			break;
		}
        
        // 계산된 피연산자 제거 및 값 업데이트
		V1.erase(V1.begin() + operands_idx_left);
		V1[operands_idx_left] = cal_value;
        
        // 계산된 연산자 제거
		V2.erase(V2.begin() + operators_idx);
		del_cnt++;
	}

	// Test Code
	/*cout << "우선순위 계산된 수식 : ";
	for (int i = 0; i < V1.size(); i++)
		cout << V1[i] << " ";
	cout << "\n";
	cout << "남은 수식 : ";
	for (int i = 0; i < V2.size(); i++)
		cout << V2[i] << " ";
	cout << "\n";*/

	// 남은 수식 계산
	int idx = 0;
	int value = 0;
	while (idx < V2.size()){
		switch (V2[idx]){
		case '+':
			value = V1[idx] + V1[idx + 1];
			break;
		case '-':
			value = V1[idx] - V1[idx + 1];
			break;
		case '*':
			value = V1[idx] * V1[idx + 1];
			break;
		default:
			cout << "error2\n";
			break;
		}

		idx++;
		V1[idx] = value;
	}

	//cout << "계산값 : " << V1[idx] << "\n\n";

	if (max_answer <= V1[idx])
		max_answer = V1[idx];


	return;
}