백준 16637 괄호 추가하기 C++

문제

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

 

풀이

이 코드는 깊이 우선 탐색 (DFS)을 사용하여 모든 가능한 연산 순서를 확인하며 최대값을 구한다.

주어진 수식에서 괄호를 적절히 사용하여 최대 값을 찾아낸다.

코드를 실행하면 결과의 최대값이 출력된니다.

 

괄호 정하기 (괄호 안에 있는 연산자의 순서 적기)
연산자와 연산자는 두 칸 이상 띄어야한다.
예시: (3+8) * (7-9) *2
3 + 8 * 7 - 9 * 2
0 - 끝
   ㄴ2 - 끝
   ㄴ3 -끝
 1 - 끝
   ㄴ3 - 끝
 2 - 끝
 3 - 끝
괄호 먼저 순서대로 계산 -> 괄호 이외 순서대로 계산

#include <iostream>
#include <algorithm>
using namespace std;

char input[20];
int n, answer=-987654321;

int calculate(int a, int b, char oper) {
	int result = 0;
	if (oper == '+') {
		result = a + b;
	}
	else if (oper == '-') {
		result = a - b;
	}
	else if (oper == '*') {
		result = a * b;
	}
	return result;
}

void DFS(int i, int cur) {
	//종료
	if (i >= n) {
		answer = max(answer, cur);
		return;
	}
	char oper = (i > 0) ? input[i-1] : '+';
	//괄호 안 묶을 때
	DFS(i + 2, calculate(cur, input[i]-'0', oper));

	//괄호 묶을 때
	if (i + 2 < n) {
		int paranthesis = calculate(input[i] - '0', input[i + 2]-'0' , input[i + 1]);
		DFS(i + 4, calculate(cur, paranthesis, oper));
	}	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> input;


	DFS(0, 0);
	cout << answer;
	return 0;

}