문제
- 시간 제한: 0.5초
- 메모리 제한: 512MB
Problem Analysis
최대를 구하는 공식은 딱히 없다. 따라서, 모든 경우를 조사해야 한다.
Algorithm
아래 중 가능한 경우에 대해, 다음 연산자로 recursive call을 한다.
- 현재 연산자에 괄호를 치기(이전 연산자에 괄호가 없어야 가능)
- 현재 연산자에 괄호를 치지 않기
이렇게 만들어진 모든 경우를 계산해, 최대를 구한다.
Data Structure
- bracket_flag: 괄호가 있는 연산자를 나타내기 위한 값, bitmasking 이용
결과
Other
시간 복잡도는 O(2^M)이다 (M=연산자의 개수). 그러나, 괄호를 연속으로 칠 수 없기 때문에 실제는 더 빠르다.
