백준 16639번 괄호 추가하기 3

문제 링크입니다: https://www.acmicpc.net/problem/16639

16639번: 괄호 추가하기 3

기존 괄호 추가하기 2(https://jaimemin.tistory.com/1455)와 유사해 보이지만 전혀 다른 문제였습니다.

중첩 괄호가 가능하기 때문에 문제에서 언급한 아래의 조건을 무시할 수 있기 때문입니다.

1. 연산자 간 우선순위가 다르다

2. 괄호 내 여러 개의 연산자가 들어 있어도 된다.

 

이유는 즉슨 괄호를 원하는 순서대로 묶어주면 되기 때문입니다.

예를 들어 3 * 5 + 4라는 식이 있다면 연산자 간 우선순위를 유지하도록 ((3 * 5) + 4)와 같이 묶을 수도 있고 우선순위를 무시하도록 (3 * (5 + 4))와 같이 묶을 수 있습니다.

괄호 내 여러 개의 연산자가 있더라도 해당 괄호 내 또 괄호를 쳐줌으로써 조건을 무시할 수 있습니다.

 

따라서 알고리즘은 아래와 같습니다.

1. i 번째 숫자부터 j 번째 숫자까지 연산을 한 결과의 최댓값과 최솟값을 저장하는 maxCache 배열과 minCache 이중 배열을 선언합니다.

2. 최종 결과의 최댓값이 음수 * 음수 일 가능성도 있기 때문에 아래와 같이 네 가지 경우의 수를 고려하며 [0, N/2 + 1)까지의 결과를 계산합니다.

i) calculate(최댓값, 최댓값)

ii) calculate(최댓값, 최솟값)

iii) calculate(최솟값, 최댓값)

iV) calculate(최솟값, 최솟값)

3. 최종 결과는 maxCache[0][N/2] 에 저장되어 있습니다.

 

N의 범위가 최대 19이기 때문에 시간복잡도가 O(N^3)이라도 시간 안에 돌아간다는 것은 자명합니다!

 

	#include <iostream>
	#include <string>
	#include <algorithm>
	#include <cstring>
	#include <climits>
	using namespace std;
	const int MAX = 10;
	int N;
	string s;
	// [i, j] 범위 내 연산 최댓값, 최솟값
	int maxCache[MAX][MAX];
	int minCache[MAX][MAX];
	void initialize(void)
	{
	for (int i = 0; i < MAX; i++)
	{
	for (int j = 0; j < MAX; j++)
	{
	maxCache[i][j] = INT_MIN;
	minCache[i][j] = INT_MAX;
	}
	}
	}
	int calculate(int a, int b, char op)
	{
	switch (op)
	{
	case '+':
	return a + b;
	case '-':
	return a - b;
	case '*':
	return a * b;
	}
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	cin >> s;
	initialize();
	int numberCnt = N / 2 + 1;
	for (int i = 0; i < numberCnt; i++)
	{
	maxCache[i][i] = minCache[i][i] = s[i * 2] - '0';
	}
	for (int cnt = 1; cnt < numberCnt; cnt++)
	{
	for (int idx = 0; idx < numberCnt - cnt; idx++)
	{
	for (int i = 1, j = cnt; i <= cnt; i++, j--)
	{
	int opIdx = (idx + cnt - j) * 2 + 1;
	char op = s[opIdx];
	int candidates[4] = {
	calculate(maxCache[idx][idx + cnt - j], maxCache[idx + i][idx + cnt], op),
	calculate(maxCache[idx][idx + cnt - j], minCache[idx + i][idx + cnt], op),
	calculate(minCache[idx][idx + cnt - j], maxCache[idx + i][idx + cnt], op),
	calculate(minCache[idx][idx + cnt - j], minCache[idx + i][idx + cnt], op)
	};
	sort(candidates, candidates + 4);
	maxCache[idx][idx + cnt] = max(maxCache[idx][idx + cnt], candidates[3]);
	minCache[idx][idx + cnt] = min(minCache[idx][idx + cnt], candidates[0]);
	}
	}
	}
	int result = maxCache[0][numberCnt - 1];
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~