백준 16637번 괄호 추가하기 (삼성 A형)

문제

길이가 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 과정을 잘 생각해야 하는 문제.

이전에도 비슷한 문제를 풀어본 적이 있었던 것 같으나, 잘 기억이 안났다...

 

O v O v O v O v O v O

이렇게 연산이 있을 때 v는 연산자 O가 숫자라고 하면,

기본적으로 진행되는 DFS 방향이 있다.

왼쪽부터 오른쪽으로 차근 차근 이동하는 방법.

그리고

1. O v (O v O) v O v O v O

2. O v O v (O v O) v O v O

3. O v O v O v (O v O) v O

4. O v O v O v O v (O v O)

와 같이 하나의 괄호로 묶이는 경우

1. O v (O v O) v (O v O) v O

2. O v (O v O) v O v (O v O)

3. O v O v (O v O) v (O v O)

혹은 두개의 괄호로 묶이는 경우 

어떠한 경우에도 조그만 잘 생각해보면

괄호 바로 이전의 연산자를 제외한 그 이전의 숫자와 연산자는 이미 처리되있는 상태에서 괄호가 연산되고

연산된 괄호와 이미 처리된 이전 숫자들이 그 사이 연산자로 연산되는 과정이다.

즉 기본적으로 진행하는 상황에서 자신의 차례의 연산자가 아닌 그 이후 연산자에 대한 계산을 먼저 하고

자신의 차례 숫자와 ,연산자 그리고 처리된 이후 연산자의 값을 연산하게 되는 경우로 모든 케이스를 구분지을 수 있다.

 

연산자 한개로 묶을 수 있는 경우를 보면

1번의 경우 시작단계에서 이후 연산자 먼저 처리 후 자신과 연산 이후 일반적 진행

2번의 경우 일반적 진행 후 이후 연산자 먼저 처리후 자신과 연산 이후 일반적 진행

3,4 다 마찬가지 방식이다.

 

그리고 두개씩 묶인 것 또한 한개씩 묶인 것이 DFS과정으로 처리된 후 똑같은 방식으로 진행되는 DFS이므로 

모두 처리 가능하다.

 

즉 일반적으로 진행하는 DFS가 흘러가고 그 안에 바로 다음 연산자에 대한 괄호로 묶어주는 과정이 추가 되면 

모든 케이스가 분류 가능해 진다.

 

 

 

 

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

int N;
vector<char> cvec;
vector<int> ivec;
long long result = -987654321987654321;
string str;


long long cal(int cur, int idx, int next)
{
	if(cvec[idx] == '+')
	{
		return cur + next;
	}
	else if(cvec[idx] == '-')
	{
		return cur - next;
	}
	else if(cvec[idx] == '*')
	{
		return cur * next;
	}
	
	
}

void DFS(long long cur, int idx)
{
	
	if(idx >= cvec.size())
	{
		if(cur > result)
		{
			result = cur;
		}
		return;
	}
	
	long long cost = cal(cur,idx,ivec[idx+1]);
	DFS(cost,idx+1);
	
	
	if(idx+1 < cvec.size())
	{
		long long nextcost = cal(ivec[idx+1],idx+1,ivec[idx+2]);
		long long realcost = cal(cur,idx,nextcost);
		DFS(realcost,idx+2);
	}
	
	
}


int main(void)
{
	
	cin  >> N;
	cin >> str;
	
	
	for(int i = 0; i < N; i++)
	{
		if(str[i] == '+' || str[i] == '*' || str[i] == '-')
		{
			cvec.push_back(str[i]);
		}
		else
		{
			ivec.push_back(str[i]-'0');
		}
		
	}
	
	if(cvec.size() == 0)
	{
		cout << ivec[0] << endl;
		return 0;
	}
	
	
	DFS(ivec[0],0);
	
	cout << result << endl;
	
	
}