백준 16637번: 괄호 추가하기

[문제 링크]

16637번: 괄호 추가하기

---

입력의 크기가 크지 않음에도 불구하고 동적계획법으로 접근했다가 풀이까지 오래걸린 문제였다.

 

경우의 수는 두가지로 나뉜다.

1. 현재 숫자와 다음 숫자 사이를 괄호로 묶었을 때 최댓값

2. 다음 숫자와 그 다음 숫자 사이를 괄호로 묶었을 때 최댓값

ex) 1 + 2 * 3 -> (1 + 2) * 3 || 1 + (2 * 3)

 

위 경우의 수를 모두 고려하여 최댓값을 찾아주면 원하는 결과를 얻을 수 있다.

---

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

const int INF = 987654321;
string str;
int N, result = -INF;

int max(int a, int b) { return a > b ? a : b; }

int Calc(int first, int second, char oper)
{
	switch (oper)
	{
	case '+':
		return first + second;

	case '-':
		return first - second;

	case '*':
		return first * second;
	}
}

void Solution(int here, int sum)
{
	if (here > N - 1)
	{
		result = max(result, sum);
		return;
	}
	
	int firNum = sum;
	int secNum = str[here + 1] - '0';
	
	Solution(here + 2, Calc(firNum, secNum, str[here]));

	if (here + 2 < N)
	{
		int thirdNum = str[here + 3] - '0';
		Solution(here + 4, Calc(firNum, Calc(secNum, thirdNum, str[here + 2]), str[here]));
	}
}

int main(void)
{
	cin >> N;
	cin >> str;

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

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 113 day