[백준 16637: 괄호 추가하기] (C++)

삼성 A형 기출 문제

https://www.acmicpc.net/workbook/view/2771

ㄴ괄호 추가하기

         https://www.acmicpc.net/problem/16637

 

 

 

l 문제

 

1. 길이가 N인 수식이 있다.

2. 수식(문자열)은 정수로 시작하고, 연산자와 정수 번갈아가며 나온다. 수식에 포함된 정수는 0이상 9이하, 연산자는 +, -, * 중 하나

3. 연산자 우선순위는 모두 동일, 수식 계산을 왼쪽에서부터 순서대로 한다. 3+8×7-9×2의 결과는 136

4. 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다.  단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 중첩된 괄호는 사용할 수 없다. 추가하는 괄호 수 제한 없다. 추가하지 않아도 됨

5. 항상 올바른 수식만 주어짐

 

 

l 연산 순서

 

1. 앞에서 부터 괄호를 묶거나 안 묶는다.

2. 만들어지는 식을 계속 계산

3. 끝에 도달하면 최댓값과 비교하여 갱신

 

 

l 입력

 

첫째 줄에 수식의 길이 N이 주어진다. N은 홀수 (1 ≤ N ≤ 19)

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

 

 

l 출력

 

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

 

 

l 예시

 

1+3*4-1+2

괄호 없음	1+3*4-1+2
괄호 1개	(1+3)*4-1+2 1+(3*4)-1+2 1+3*(4-1)+2 1+3*4-(1+2)
괄호 2개	(1+3)*(4-1)+2 (1+3)*4-(1+2) 1+(3*4)-(1+2)
괄호 3개	괄호 안에는 연산자가 하나만 존재해야 하므로 무조건 3개 단위로 묶인다. = 묶을 수 있는지 조건 검사 (1+3)*(4-1)+2 여기서는 더 이상 괄호를 묶을 수 없다. (안 묶는다. 쪽으로만 가도록 제어해야 함)

 

 

l 풀이

 

DFS로 풀 수 있다.

연산 함수 {    연산자 +, *, - 에 따라 처리 } DFS 함수 {    1. 종료 조건    2. 괄호로 묶는다. // 괄호 묶을 수 있는지 잘 확인    3. 안 묶는다. }

괄호로 묶기 괄호 안에 연산자가 1개만 포함되어야 한다는 조건에 의하여 무조건 3개 단위로 묶인다. 1. 묶을 수 있는 개수인지 확인 2. 괄호 계산    괄호 값 = ( a 연산자 b ) 꼴로 계산 됨    a = str[idx]    b = std[idx+2]    연산자 = std[idx+1] 3. 현재 값과 괄호 값을 연산    1 + ( 1 * 4 ) 이런 연산을 한다는 뜻 4. 괄호 계산에 3개, 연산에 1개를 소모했기 때문에 idx + 4 해준다.

괄호 안 묶기 1. 현재 값과 다음 값을 연산한다. 1 + 4 이런 꼴이다. 2. 연산에 1개, 다음 값에 1개 소모했기 때문에 idx + 2 해준다.

 

 

l  코드

 

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

int n, max_ans;
string str;

int cal(int a, int b, char oper)
{
	int result = a;
	switch (oper)
	{
	case '+': result += b; break;
	case '*': result *= b; break;
	case '-': result -= b; break;
	}
	return result;
}

void recur(int idx, int cur)
{
	// 1. 종료 조건
	if (idx > n - 1)
	{
		max_ans = max(max_ans, cur);
		return;
	}
	char oper = (idx == 0) ? '+' : str[idx - 1];

	// 2. 괄호로 묶는다 = 이전 + 괄호 계산
	if (idx + 2 < n)
	{
		int bracket = cal(str[idx] - '0', str[idx + 2] - '0', str[idx + 1]);
		recur(idx + 4, cal(cur, bracket, oper));
	}
	// 3. 안 묶는다 = 이전 + 다음
	recur(idx + 2, cal(cur, str[idx] - '0', oper));
}

int main()
{
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> str;

	max_ans = INT_MIN;
	recur(0, 0);
	cout << max_ans;
	return 0;
}