백준 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)이라도 시간 안에 돌아간다는 것은 자명합니다!

 

개발환경:Visual Studio 2017

 

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