[C++/백준] 16637 괄호 추가하기

16637번: 괄호 추가하기

 

[문제 요악]

 

1. 0보다 크고 9보다 작은 수와 수식( + - * )이 있다. ( 길이 <= 19 )

  - 수식의 우선순위는 동일하다. 

2. 중복 괄호를 칠 수 없고, 괄호 안에는 연산자가 하나만 들어가야 한다. 

3. 괄호를 적절하게 쳐서 최대값이 되는 값을 찾아라. 

 

[아이디어 구현 과정]

 

일단 문제를 읽고 정리하면서 풀이과정을 두 가지가 떠올랐다. 

1. 완전 탐색 

2. 트리 + 메모이제이션 (혹시..)

 

그럼 완전 탐색으로 생각해 봤을 때, 

 

첫 번쨰로 시간 복잡도를 봤다. -> 시간 제한 0.5초 -> 5000만 정도

보면 수식의 최대 길이가 19이고, 그 중 숫자만 뽑아낸다고 했을 떄 최대 10이다. 

 

경우를 따져보면, 내 바로 뒤에 숫자를 그 다음 숫자와 묶을 것이냐?로 분기가 나뉘어 진다. 

N 번쨰 숫자에 있을 때, N+1 번째 숫자를 그대로 연산할거냐 (N+1과 N+2를 연산) 하고 더할거냐 

이런식인데 이렇게 계산하면 2^10 정도 겠구만~ 그럼 천번 정도의 경우가 나오는데, 

이정도는 완전 탐색으로 가능하겠다고 생각했다. 

 

[코드]

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int N, max_V=-2e9;
vector<char> num; // 숫자 넣음
vector<char> op; // OPERATOR 넣음

int calculator(int  n1, int n2, char _op) {
	if (_op == '+')
		return n1 + n2;
	if (_op == '-')
		return n1 - n2;
	if (_op == '*')
		return n1 * n2;
}

/* 
* idx1 : 이번에 더할 숫자 
* idx2 : 이번에 사용할 연산자
* result : 이 전까지 더한 결과
*/
void find_max(int idx1, int idx2, int result) {
	// 기저 조건 : 숫자가 더 이상 없을 때
	if (idx1 >= num.size()) {
		max_V = max(max_V, result);
		return;
	}

	int f; // 임시로 값을 담음
	f = calculator(result, num[idx1], op[idx2]);
	
	// 괄호 없이 더한 경우
	find_max(idx1 + 1, idx2 + 1, f);
	
	// 괄호를 사용하기 전에, 마지막 숫자면 ㄴㄴ 
	if (idx1 + 1 >= num.size())
		return;
	
	// 괄호를 사용한 경우
	f = calculator(result, calculator(num[idx1], num[idx1 + 1], op[idx2 + 1]),op[idx2]);
	
	find_max(idx1 + 2, idx2 + 2, f);
}


int main() {
	cin >> N;
	string s;
	cin >> s;
	for (int i = 0; i < N; i++) {
		if (s[i] >= '0' && s[i] <= '9')
			num.push_back(int(s[i]-'0'));
		else
			op.push_back(s[i]);
	}

	find_max(1, 0, num[0]);

	cout << max_V;

	return 0;

}