문제 요약
- 수식이 주어짐. 길이 19
- +, -, x 만 주어지고 0 ~ 9 숫자만 주어짐
- 적절히 괄호 추가했을 때 최대값
접근법
- 처음에는 완전탐색으로 접근해보려고 했음 : (없음, 여는, 닫는) ^ n 경우의수
- 수식을 두개로 쪼개서 (l, r)을 잘 구했다 치고.. 로 접근함
- (l, r) 구간의 최대값을 잘 구하면 되겠다고 생각
- 수식이 주어지면 적당히 나눠서 (왼쪽), (오른쪽) 의 최적을 구하고 둘을 연산
- 테스트케이스는 맞았으나 제출하면 실패
- 곱하기의 경우 음 * 음 = 양이 되므로 최소값도 유지
- dp[l][r] = (l ~ r) 수식의 최소값, 최대값
구현
- python eval() 함수를 적절히 응용함
newbieski