[programmers][찾아라 프로그래밍 마에스터] 사칙연산

문제 : programmers.co.kr/learn/courses/30/lessons/1843

---

숫자와 연산 기호(+, -)로 이루어진 수식이 주어질 때 괄호를 추가해 그 수식의 계산 결과는 여러가지가 나올 수 있다.

이 때 나올 수 있는 계산 결과 중 최대값을 구하여라.

---

DP로 해결했다.

수식이 문자열 arr로 주어지고 부분문자열 arr[s~e]의 최대값, 최소값을 저장하는 배열을 만든다.

최대값 배열 dMax[s][e] = arr[s~e] 수식의 계산 결과 중 최대값.

최소값 배열 dMin[s][e] = arr[s~e] 수식의 계산 결과 중 최소값.

우리가 알고자 하는 값은 dMax[0][n-1] 인데 최대값을 구하기 위해서는 최소값도 알아야 하기 때문에 dMin 배열도 필요하다.

 

만약 i 인덱스가 연산 기호인 경우 dMax[s][e]는 다음과 같다.

i) arr[i] == '+' 

dMax[s][e] = dMax[s][i-1] + dMax[i+1][e]

ii) arr[i] == '-'

dMax[s][e] = dMax[s][i-1] - dMin[i+1][e]

기호가 음수인 경우 가장 작은수가 가장 큰 수가 되기 때문에 dMin 배열을 참조하게 된다.

 

i 인덱스가 연산 기호인 경우 dMin[s][e]는 다음과 같다.

i) arr[i] == '+'

dMin[s][e] = dMin[s][i-1] + dMin[i+1][e]

ii) arr[i] == '-'

dMin[s][e] = dMin[s][i-1] - dMax[i+1][e]

최소값 배열도 마찬가지로 - 기호인 경우 dMax 배열을 참조하게 된다.

 

이제 기호가 나오는 i 인덱스를 찾아서 위 계산 결과를 구하면 배열을 채워나갈 수 있다.

예를 들어, 1-2+5-8 인 경우 최대값은 1 - (2+5-8), (1-2) + (5-8), (1-2+5) - 8 결과 중 최대값이 된다.

이 때, i 인덱스가 될 수 있는 수는 1,3,5이다. (이게 끝이 아니라, 괄호안에 있는 수들은 다시 연산순서를 바꿔가며 나올 수 있는 최대값을 구해야 한다. 단순히 i 인덱스가 뭔지 설명하기 위해 예시를 들었다.)

따라서 기호가 될 수 있는 i를 구하기 위해 s < i < e 범위를 탐색해야 한다.

 

시간복잡도는 [s][e] 범위를 탐색하는데 N^2, 기호 i를 구하는데 드는 N까지 합쳐서 O(N^3)가 된다.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%B0%BE%EC%95%84%EB%9D%BC%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%20%EB%A7%88%EC%97%90%EC%8A%A4%ED%84%B0/%EC%82%AC%EC%B9%99%EC%97%B0%EC%82%B0.cpp