[프로그래머스] 사칙연산 - 파이썬(python)

 

 

나의 풀이

import math

def solution(arr):
    N = math.ceil(len(arr) / 2)
    # dp[] 는 피연산자만 담아둔다
    # 즉, dp[i][j] 는 i번째숫자~j번째숫자까지의 최대/최솟값이다
    max_dp = [[float('-inf') for _ in range(N)] for _ in range(N)]
    min_dp = [[float('inf') for _ in range(N)] for _ in range(N)] 
    
    for step in range(N) : # i~j 까지의 간격
        for i in range(N-step) : 
            j = i + step
            if step == 0 : # 간격이 0 일때는 자기자신이 최대/최소
                max_dp[i][i] = int(arr[i*2]) 
                min_dp[i][i] = int(arr[i*2])
             
            else :
                for k in range(i,j) : # i~j까지 최대/최소 연산을 하기 위해 i와 j 사이에 있는 k까지로 괄호를 나눠서 계산한다
                # 즉, (i~k) + (k+1~j) 를 계산하며, 괄호의 위치를 변경하며 i~j가 최대/최소값을 찾는다
                # ex) 1-(3+5) / (1-3)+5
      
                # 만약 k번째 숫자 오른쪽 연산이 + 라면 ()+()
                    if arr[k*2+1] == '+' :
                        max_dp[i][j] = max(max_dp[i][j],max_dp[i][k] + max_dp[k+1][j]) # 최댓값 = 최댓값 + 최댓값
                        min_dp[i][j] = min(min_dp[i][j],min_dp[i][k] + min_dp[k+1][j]) # 최솟값 = 최솟값 + 최솟값
                
                    else : # 오른쪽 연산자가 - 라면 ()-()
                        max_dp[i][j] = max(max_dp[i][j],max_dp[i][k] - min_dp[k+1][j]) # 최댓값 = 최댓값 - 최솟값
                        min_dp[i][j] = min(min_dp[i][j],min_dp[i][k] - max_dp[k+1][j]) # 최솟값 = 최솟값 - 최댓값
                 
    
    return max_dp[0][N-1]

DP 는 큰 문제를 해결하기 위해 작은 문제들의 답을 미리 저장해놓고, 그것을 이용하여 푸는 문제이다.

위 문제에는 괄호 때문에 엄청나게 많은 경우의 수가 있다. 

 

1-3+5-8 을 예시로 들자. 

여기서 피연산자만 추출하면, 1 3 5 8 이 되며, 피연산자의 갯수만큼 dp[][] 를 생성한다.

dp[i][j] 는 i번째숫자부터 j번째 숫자까지 계산했을 때의 최대/최소값이 저장되어 있다.

 

• step 이라는 변수를 두어 i~j 까지의 간격을 설정한다.
• 먼저 step 이 0 일때에는 i~i까지의 계산결과이므로 항상 자기자신이 들어가게 된다.

 

• step 이 1일 때에는 i~i+1 까지의 계산결과이므로, i와 i+1 사이에 있는 연산자에 맞게 계산만 하면 된다.

 

• step 이 2일 때에는 1-3+5 혹은 3+5-8 을 계산해야 하는 경우이다.
• 이때는 k라는 변수를 두어 괄호의 위치를 오른쪽으로 옮겨가며 i~j까지의 최대/최소 결과값을 찾는다.
• 즉, (i~k 까지의 결과값) + (k+1~j) 과 기존의 dp[i][j] 값을 비교하며 최대/최소 값으로 갱신해야 한다.
• ex) k=0일때, 1-(3+5) = -7
• k=1일때, (1-3)+5 = 3
• 이므로 max_dp[0][2] 는 3이 된다.

 

이렇게 0~N-1 을 구하기 위해

i~j 까지로 나누어 부분계산하고,

i~j까지의 최대/최소를 구하기 위해 괄호를 하나씩 이동시키며 i~k / k+1~j 로 나누어 계산하는 것이 전반적인 알고리즘이다.

 

 

처음에 갈피를 잡지 못해 https://school.programmers.co.kr/questions/35224 에서 많은 도움을 얻었다.

세상에는 똑똑한 사람이 정말 많다.