boj, 백준) 16637 괄호 추가하기 (C / C++)

1. 문제 링크

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

16637번: 괄호 추가하기

2. 문제 개요

주어진 수식에 괄호를 적절히 추가하여 결과의 최댓값을 출력하기.

 

3. 문제 힌트!!

   DFS를 사용하여 Bruteforce형식으로 풀이함.

 

4. 문제 풀이

 

3+8*7-9*2를 예로,

할 수 있는 조합은

1. (3+8)*(7-9)*2

2. (3+8)*7-(9*2)

3. 3+(8*7)-(9*2)

4. 3+8*(7-9)*2

5. 3+8*7-(9*2)

6. 3+8*7-9*2

가 있다.

 

입력 수식을 char변수로 받았을 경우에는 1번째에 괄호를 친다고 가정하면 다음 괄호는 적어도 5번 원소부터 할 수 있다.

그리고 수식의 길이가 n일때, 괄호는 n-2항까지만 할 수 있다.(여는 괄호 기준)

이점을 유의해서 DFS를 구현했다.

 

괄호를 관리하는 배열을 따로 한 개 더 선언하여 괄호를 처리하도록 한다.

개념은 간단하나 이걸 어떻게 코드로 잘 옮길 수 있느냐가 관건인 문제인 것 같다.

 

5. 코드

#include <stdio.h>
#include <algorithm>
using namespace std;

char val[20];
int n;
bool selected[20];
long long int ret = -0x7fffffff;
long long int cal(long long int a, long long int b, char op)
{
	if (op == '+')
		return a + b;
	else if (op == '-')
		return a - b;
	else if (op == '*')
		return a * b;
	else if (op == '/')
		return a / b;
}

void dfs(int depth,int start, int limit)
{
	if (depth == limit)
	{
		//괄호 처리하기.
		long long int sum = val[0]-'0';

		for (int i = 1; i < n;)
		{
			//괄호가 있다면,
			if (selected[i +1])
			{
				long long int temp;
				temp = cal(val[i + 1]-'0', val[i + 3]-'0', val[i + 2]);
				sum = cal(sum, temp, val[i]);
				i += 4;
			}
			else
			{
				sum = cal(sum, val[i + 1] - '0', val[i]);
				i += 2;
			}
		}

		ret = max(ret, sum);

		return;
	}
	for (int i = start; i < n-2; i=i+2)
	{
		selected[i] = true;
		dfs(depth + 1, i + 4, limit);
		selected[i]= false;
	}
}
int main(void)
{
	scanf("%d", &n);
	scanf("%s", val);

	//연산자 기준으로  dfs..

	for (int i = 0; i <=n/2 ; i++)
		dfs(0,2,i);

	printf("%lld", ret);
	return 0;
}

지적, 댓글 언제나 환영입니다~