[백준] 16637번 괄호 추가하기

16637번: 괄호 추가하기

1. 괄호로 묶지 않는 경우

이전까지의 값 OP 숫자

= res a[idx] a[idx+1]

 

2. 괄호로 묶는 경우

이전까지의 값 OP (숫자 OP 숫자)

= res a[idx] (a[idx+1] a[idx+2] a[idx+3])

 

재귀 호출을 이용해  수식의 처음부터 끝까지 돌면서

1번 경우는 무조건 계산하고

2번 경우는 뒤에 남은 수식이

괄호를 추가할 수 있을 만큼 남아있는 경우에만 계산한다.

#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
int N, Max = INT_MIN;
string a;

int cal(int a, char op, int b) {
	switch (op) {
	case '+':
		return a + b;
	case '-':
		return a - b;
	case '*':
		return a * b;
	}
}

void Solution(int idx, int res) {
	if (idx > N - 1) {
		Max = max(Max, res);
		return;
	}
	if (idx + 4 <= N) { // 괄호로 묶을 수 있는 경우
		Solution(idx + 4, cal(res, a[idx], cal(a[idx + 1] - '0', a[idx + 2], a[idx + 3] - '0')));
	}
	Solution(idx + 2, cal(res, a[idx], a[idx + 1] - '0'));
}

int main() {
	cin >> N >> a;

	Solution(1, a[0] - '0');

	cout << Max;

	return 0;
}