문제 링크입니다: https://www.acmicpc.net/problem/16639
기존 괄호 추가하기 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
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 17837번 새로운 게임 2 (0) | 2020.05.27 |
---|---|
백준 17822번 원판 돌리기 (0) | 2020.05.26 |
백준 1408번 24 (0) | 2020.05.26 |
백준 16638번 괄호 추가하기 2 (0) | 2020.05.24 |
백준 16637번 괄호 추가하기 (6) | 2020.05.24 |