[동적계획법] 사칙연산

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

프로그래머스

---

문제 설명
사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 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 입니다.

---

뺄셈의 특징을 고려해서 연산을 하는 문제입니다.

 

덧셈 연산은 대칭성이 있어, 최댓값끼리 더해주면 최댓값이 되고, 최솟값끼리 더해주면 최솟값이 됩니다.

반면 뺄셈 연산은 비대칭성 때문에, 최댓값과 최솟값을 빼야 최댓값이 되고, 최솟값에서 최댓값을 빼야 최솟값이 됩니다.

 

따라서 이 문제에서는 최댓값과 최솟값을 같이 관리해줘야만 뺄셈 연산을 제대로 할 수 있으므로, dp_max 배열과 dp_min 배열을 활용해 최댓값과 최솟값을 같이 관리해주겠습니다.

 

초기화 부분의 코드는 다음과 같습니다.

# 숫자의 개수만큼 DP 테이블을 생성합니다.
# 숫자는 짝수, 연산자는 홀수입니다.
n = len(arr) // 2 + 1

# DP 테이블 초기화
# 뺄셈 연산을 위해 최댓값과 최솟값을 동시에 관리합니다.
dp_max = [[-float('inf')] * n for _ in range(n)]
dp_min = [[float('inf')] * n for _ in range(n)]

# 숫자들로 DP 초기화
# dp_max[i][j]: i번째 숫자부터 j번째 숫자까지 활용해 만든 수식에서 얻을 수 있는 최댓값
# dp_min[i][j]: i번째 숫자부터 j번째 숫자까지 활용해 만든 수식에서 얻을 수 있는 최솟값
for i in range(n):
    # dp_max[i][i], dp_min[i][i]는 i번째 숫자만 활용해 만들었으므로 숫자로 초기화합니다.
    dp_max[i][i] = dp_min[i][i] = int(arr[2 * i])

문자열에서 숫자는 항상 짝수, 연산자는 항상 홀수 인덱스에 위치합니다.

숫자가 처음 등장하고, 숫자와 연산자가 번갈아 가면서 등장하기 때문입니다.

 

dp_max, dp_min 배열은 기본값으로 각각 -inf, inf로 초기화합니다.

음의 무한대보다 작거나, 양의 무한대보다 큰 경우는 없기 때문에 관리가 쉬워집니다.

 

그 다음, 숫자들을 dp_max, dp_min 배열에 넣습니다.

두 배열은 이중 리스트 구조인데요, 두 배열의 인덱스 (i, j)에는 i번째 숫자부터 j번째 숫자까지의 부분 수식으로 만들 수 있는 최댓값과 최솟값을 저장합니다.

초기화를 해줄 때는 i번째 숫자만 활용하므로 해당하는 인덱스인 2 * i의 값으로 초기화해줍니다.

---

이제 부분 수식을 구현해서 dp_max, dp_min 배열을 채워보겠습니다.

dp_max[i][j], dp_min[i][j]는 i번째 숫자부터 j번째 숫자까지 사용해 만든 부분 수식의 최댓값, 최솟값을 의미합니다.

 

부분 수식의 길이는 연산자에 의해 결정됩니다.

연산자가 1개라면 부분 수식은 두 숫자 사이의 연산을, 2개라면 부분 수식은 세 숫자 사이의 연산을 의미합니다.

다시 말해 연산자가 n개인 부분 수식은 (n + 1)개의 숫자 사이의 연산을 나타내는 거죠.

이 문제에서는 연산자의 숫자는 (n - 1)개이므로, 부분 수식의 길이 역시 1부터 (n - 1)개가 최대입니다.

# 부분 수식으로 나누어 값을 구합니다.
# 부분 수식은 연산자의 개수에 따라 길이가 정해집니다.
for size in range(1, n): # 연산자의 최대 개수는 (n - 1)개

---

부분 수식의 길이를 설정했다면, 그 다음은 해당 부분 수식에 쓰일 숫자들을 구하는 과정입니다.

dp 배열들에서 이미 i - j의 관계를 설정해두었기 때문에, i, j를 어떻게 구할지만 고민하면 됩니다.

 

size의 크기에 커질 수록, 시작점으로 사용할 수 있는 i의 개수가 줄어듭니다.

1번 예제를 기준으로 생각해보겠습니다.

size = 1일 때, 1 - 3 + 5 - 8의 부분 수식은 총 3가지 입니다.

1. 1 - 3 (연산자 '-')

2. 3 + 5 (연산자 '+')

3. 5 - 8 (연산자 '-')

 

size = 2일 때, 1 - 3 + 5 - 8의 부분 수식은 총 2가지입니다.

1. 1 - 3 + 5 (연산자 '-', '+')

2. 3 + 5 - 8 (연산자 '+', '-')

 

size = 3일 때,1 - 3 + 5 - 8의 부분 수식은 총 3가지입니다.

1. 1 - 3 + 5 - 8 (연산자 '-', '+', '-')

 

i가 시작점으로 사용할 수 있는 위치는 최대 (n - size - 1)개까지라는 걸 볼 수 있습니다. 최대 size는 n - 1까지니까요.

    # 연산자의 개수에 따라 나올 수 있는 수식의 개수
    # 인덱스의 시작점 i
    for i in range(n - size):

---

이제 끝점이 되는 j에 대해서 알아보겠습니다.

j는 간단한 게, i에 size를 더해주면 됩니다.

앞에서 계속 언급했다시피, 숫자는 size + 1개만큼 필요합니다. 여기서는 이미 i번째 숫자는 사용하는 게 확정이기 때문에, size만큼 늘려주면 총 숫자가 (size + 1)개가 됩니다.

        # 인덱스의 끝점 j
        j = i + size

---

이제 i번째 숫자부터 j번째 숫자까지의 부분 수식에서 최댓값, 최솟값을 구하겠습니다.

k 변수를 활용해서 i부터 (j - 1)까지의 반복을 실행하겠습니다.

        # i번째 숫자부터 j번째 숫자까지 사용합니다.
        for k in range(i, j):

 

 

그다음은 연산자를 구해야 하는데요, 연산자는 언제나 홀수 인덱스에 위치하고 있기 때문에 계산하기 쉽습니다.

            # 연산자가 덧셈일 경우
            if arr[2 * k + 1] == '+':
                # 최댓값 = 최댓값 + 최댓값
                # 최솟값 = 최솟값 + 최솟값
                dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j])
                dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j])
            # 연산자가 뺄셈일 경우
            elif arr[2 * k + 1] == '-':
                # 최댓값 = 최댓값 - 최솟값
                # 최솟값 = 최솟값 - 최댓값
                dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] - dp_min[k + 1][j])
                dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] - dp_max[k + 1][j])

i와 k번째 숫자들을 비교해서 각각 덧셈 연산, 뺄셈 연산을 한 결과들을 dp 배열들에 저장합니다.

---

최종적으로 작성한 코드는 다음과 같습니다.

def solution(arr):
    # 숫자의 개수만큼 DP 테이블을 생성합니다.
    # 숫자는 짝수, 연산자는 홀수입니다.
    n = len(arr) // 2 + 1
    
    # DP 테이블 초기화
    # 뺄셈 연산을 위해 최댓값과 최솟값을 동시에 관리합니다.
    dp_max = [[-float('inf')] * n for _ in range(n)]
    dp_min = [[float('inf')] * n for _ in range(n)]
    
    # 숫자들로 DP 초기화
    # dp_max[i][j]: i번째 숫자부터 j번째 숫자까지 활용해 만든 수식에서 얻을 수 있는 최댓값
    # dp_min[i][j]: i번째 숫자부터 j번째 숫자까지 활용해 만든 수식에서 얻을 수 있는 최솟값
    for i in range(n):
        # dp_max[i][i], dp_min[i][i]는 i번째 숫자만 활용해 만들었으므로 숫자로 초기화합니다.
        dp_max[i][i] = dp_min[i][i] = int(arr[2 * i])
    
    # 부분 수식으로 나누어 값을 구합니다.
    # 부분 수식은 연산자의 개수에 따라 길이가 정해집니다.
    for size in range(1, n): # 연산자의 최대 개수는 (n - 1)개
        # 연산자의 개수에 따라 나올 수 있는 수식의 개수
        # 인덱스의 시작점 i
        for i in range(n - size):
            # 인덱스의 끝점 j
            j = i + size
            # i번째 숫자부터 j번째 숫자까지 사용합니다.
            for k in range(i, j):
                # 연산자가 덧셈일 경우
                if arr[2 * k + 1] == '+':
                    # 최댓값 = 최댓값 + 최댓값
                    # 최솟값 = 최솟값 + 최솟값
                    dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j])
                    dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j])
                # 연산자가 뺄셈일 경우
                elif arr[2 * k + 1] == '-':
                    # 최댓값 = 최댓값 - 최솟값
                    # 최솟값 = 최솟값 - 최댓값
                    dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] - dp_min[k + 1][j])
                    dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] - dp_max[k + 1][j])
    # 모든 숫자를 사용했을 때 얻는 최댓값 반환
    return dp_max[0][n - 1]

 

난이도가 높은 문제라고 생각합니다. 어려웠어요.