[프로그래머스] 사칙연산

https://school.programmers.co.kr/learn/courses/30/lessons/1843

아무리 고민해도 답이 없어서 검색해서 블로그들을 참고해서 풀었다.

참고한 블로그

전체 식을 부분부분 나눠서 구간별로 먼저 계산한 결과의 최대값과 최소값을 뽑아낸 다음 적절히 계산해서 결과를 뽑아내는 방식인 것 같다.

점화식은

max_dp[i][j] = max(max_dp[i][j], 
				   calculate(max_dp[i][mid], max_dp[mid][j], operator))
min_dp[i][j] = min(min_dp[i][j],
				   calculate(min_dp[i][mid], min_dp[mid][j], operator))

이런느낌으로 나오는 것 같다. 저기서 calculate함수는 그냥 덧셈, 뺄셈만 해주는 함수인데 코드에서는 if문으로 처리했다.

    nums = []
    ops = []
    
    for a in arr:
        try:
            nums.append(int(a))
        except:
            ops.append(a)

먼저 숫자와 연산자를 분리해줬다. 조건문으로 a == '+' or a == '-'라는 조건을 걸어서 구분 시켜줘도 되는데 try-except가 더 짧아보여서 그냥 저렇게 했다.

    max_dp = [[-1001] * n for _ in range(n)]
    min_dp = [[1001] * n for _ in range(n)]

연산 결과의 최대와 최소값을 적을 배열을 만들었다. i와 j라는 인덱스가 있을 때 i와 j사이 연산의 결과 중 최대값을 max_dp[i][j]에서 찾을 수 있다. 이렇게 함으로써 덧셈에서는 최대값을 뺄셈에서는 최소값을 꺼내서 계산할 수 있게 된다.

for length in range(n):
	for i in range(n-length):
    	j = i + length
        	if i == j:
                max_dp[i][j] = min_dp[i][j] = nums[i]
                continue
            for mid in range(i, j):
				if ops[mid] == '+':
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][mid] + max_dp[mid+1][j])
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][mid] + min_dp[mid+1][j])
                elif ops[mid] == '-':
                    max_dp[i][j] = max(max_dp[i][j], min_dp[i][mid] - max_dp[mid+1][j])
                    min_dp[i][j] = min(min_dp[i][j], max_dp[i][mid] - min_dp[mid+1][j])

길이별로 돌면서 dp메모리를 채우는데 점화식에 따라서 계산 결과를 저장한다. 뺄셈일 때는 최소, 최대값을 만들기 위해서 최소 - 최대, 최대 - 최소의 순서로 연산 했다.

마지막으로는 최대값인 max_dp의 0부터 맨 마지막까지 연산 결과를 주기 위해서 max_dp[0][-1]을 반환해줬다.

테스트케이스는 대부분 통과했으나 첫번째 테스트케이스에서 통과하지 못하길래 최초의 최대값을 1001에서 2000으로 변경해주니까 통과했다. 나중에도 더미값을 넣을 때 최대값의 몇 배를 한 값을 넣어줘야겠다.

def solution(arr):
    answer = -1
    
    nums = []
    ops = []
    
    for a in arr:
        if a == '+' or a == '-':
            ops.append(a)
        else:
            nums.append(int(a))
            
    n = len(nums)
    
    max_dp = [[-2000] * n for _ in range(n)]
    min_dp = [[2000] * n for _ in range(n)]
    
    for length in range(n):
        for i in range(n-length):
            j = i + length
            if i == j:
                max_dp[i][j] = min_dp[i][j] = nums[i]
                continue
            for mid in range(i, j):
                if ops[mid] == '+':
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][mid] + max_dp[mid+1][j])
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][mid] + min_dp[mid+1][j])
                elif ops[mid] == '-':
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][mid] - max_dp[mid+1][j])
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][mid] - min_dp[mid+1][j])
    
    return max_dp[0][-1]