[프로그래머스] - 사칙연산 (LEVEL 4)

프로그래머스 사칙연산 파이썬

programmers.co.kr/learn/courses/30/lessons/1843?language=python3

코딩테스트 연습 - 사칙연산

숫자와 '+', '-'만 있는 연산에서 결합 법칙이 성립하지 않는 '-'에 대해 연산 순서에 따른 결과의 최댓값을 출력하는 문제

1. 연산 f의 최댓값을 구해야 한다

2. f가 덧셈만으로 이루어져 있을 경우 순서 그대로 연산하면 되기 때문에 return eval(f)

3. f = f(x)-f(y)일 때, 최댓값은 min(f(y))인 경우

4. f = f(x)-f(y) = f(x) - (y - f(z)) 일 때, 최댓값은 max(f(z))인 경우

 

<Solution>

'+'나 '-'를 기준으로 앞뒤로 나눠서 재귀

'-'를 만나면 min <-> max를 바꿔줌

import functools
def solution(a):
    @functools.lru_cache(maxsize=None)
    def solve(l,r,minus):
        if r-l<=1: return int(a[l])
        if minus:
            tmp = min(solve(l,i,minus)-solve(i+1,r,not minus) if a[i]=='-' else
                       solve(l,i,minus)+solve(i+1,r,minus) for i in range(l+1,r,2))
        else:
            tmp = max(solve(l,i,minus)-solve(i+1,r,not minus) if a[i]=='-' else
                       solve(l,i,minus)+solve(i+1,r,minus) for i in range(l+1,r,2))
        return tmp
    return solve(0,len(a),False)