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

문제 링크

 

문제 설명

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.

• ((1 - 5) - 3) = -7
• (1 - (5 - 3)) = -1

위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다.
또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.

• (((1 - 3) + 5) - 8) = -5
• ((1 - (3 + 5)) - 8) = -15
• (1 - ((3 + 5) - 8)) = 1
• (1 - (3 + (5 - 8))) = 1
• ((1 - 3) + (5 - 8)) = -5

위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다.
문자열 형태의 숫자와, 더하기 기호("+"), 뺄셈 기호("-")가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• arr는 두 연산자 "+", "-" 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
  • arr의 길이는 항상 홀수입니다.
  • arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
  • 숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : "456")
• 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

---

입출력 예

arr	result
["1", "-", "3", "+", "5", "-", "8"]	1
["5", "-", "3", "+", "1", "+", "2", "-", "4"]	3

입출력 예시

입출력 예 #1
위의 예시와 같이 (1-(3+(5-8))) = 1 입니다.

입출력 예 #2
(5-(3+((1+2)-4))) = 3 입니다.

---

나의 답

def solution(arr):
    num_arr = [0]
    calc_arr= [0]
    for i in arr:
        try:
            a = int(i)
            num_arr.append(a)
        except:
            if i == '-':
                calc_arr.append(-1)
            else: 
                calc_arr.append(1)
    dp_min = [[0]*(len(num_arr)+1) for _ in range(len(num_arr)+1)]
    dp_max = [[0]*(len(num_arr)+1) for _ in range(len(num_arr)+1)]
    
    # 구간 사이즈 1인거 먼저 초기화
    for i in range(1,len(num_arr)): # 자기 자신만 있는 구간 초기화
        dp_min[i][i] = num_arr[i] 
        dp_max[i][i] = num_arr[i]
        
    # 구간 사이즈 작은 것부터 초기화 해야함
    for size in range(1,len(num_arr)-1): # 5-1 = 4
        # size가 2면 1~3, 2~4 까지 가능. 이때 num_arr 크기는 5
        # end 는 num_arr -1 -size까지가 범위
        start = 1 ; end = len(num_arr) - 1 - size # 시작 인덱스의 가능 범위
        for i in range(start, end+1):
            dp_min[i][i+size] = float('inf')
            dp_max[i][i+size] = -float('inf')
            for k in range(i,i+size):
                if calc_arr[k] == -1:
                    dp_min[i][i+size] = min(dp_min[i][i+size], dp_min[i][k] - dp_max[k+1][i+size])
                    dp_max[i][i+size] = max(dp_max[i][i+size], dp_max[i][k] - dp_min[k+1][i+size])
                else: # 중간에 연산자가 + 인 경우
                    dp_min[i][i+size] = min(dp_min[i][i+size], dp_min[i][k] + dp_min[k+1][i+size])
                    dp_max[i][i+size] = max(dp_max[i][i+size], dp_max[i][k] + dp_max[k+1][i+size])
    
    return dp_max[1][len(num_arr)-1]

• 사고 과정은 아래와 같습니다. 문제 풀이에 하루가 넘게 걸린 것 같습니다..

• DP 문제라는 걸 미리 알고 있었음에도 불구하고 점화식을 세우지 못해 어려움을 겪었습니다.
• 처음에는 구간의 크기(size)를 고려하지 않고 점화식을 세우려 했고, 그로 인해 계속 답이 틀어졌습니다.문제가 복잡하다 보니, 점화식처럼 생긴 식부터 세우는 데 급급해서, 실제로 어떤 순서로 구간을 계산해야 하는지에 대한 전략적 사고가 부족했습니다.
• 이번 문제를 통해
  괄호 위치에 따라 결과가 달라지는 문제는 DP를 통해 구간별 계산 결과를 누적적으로 저장하면서 푸는 방식이 효과적이라는 걸 다시 한번 체감했습니다.
  "구간별로 최소/최댓값을 구하고 이를 조합해 더 큰 구간으로 확장해간다"는 아이디어를 기억해두면 좋을 것 같습니다.
• 예를 들어, 구간 크기가 3인 구간의 최대/최소 값을 구하려면,
  그보다 작은 구간(1, 2 크기)의 값들을 미리 구해두어야 점화식을 적용할 수 있다는 점을 간과했던 것이 원인이었습니다.