[Python][프로그래머스] 사칙연산 / DP (Lv4)

🖇️ 링크 

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

프로그래머스

---

🗒️ 파이썬 코드 풀이

def solution(arr):

    # 연산자와 숫자 분리
    operator, number = [], []
    for i in range(len(arr)):
        if i % 2 == 1: 
            operator.append(arr[i])
        else : 
            number.append(arr[i])
    number = list(map(int,number))
    
    # max, min dp 테이블 만들기
    mx_dp = [[-float('inf')] * len(number) for _ in range(len(number))]
    mn_dp = [[float('inf')] * len(number) for _ in range(len(number))]
    
    # dp 테이블 초기값 
    for q in range(len(number)):
        mx_dp[q][q] = number[q]
        mn_dp[q][q] = number[q]
    
    # dp 테이블 값 갱신 
    n = len(number) 
    for length in range(2,n+1):
        for i in range(n-length+1):
            j = i + length -1
            for k in range(i,j):
                if operator[k] == "+":
                    mx_dp[i][j] = max(mx_dp[i][j], mx_dp[i][k] + mx_dp[k+1][j])
                    mn_dp[i][j] = min(mn_dp[i][j], mn_dp[i][k] + mn_dp[k+1][j])
                else: 
                    mx_dp[i][j] = max(mx_dp[i][j], mx_dp[i][k] - mn_dp[k+1][j])
                    mn_dp[i][j] = min(mn_dp[i][j], mn_dp[i][k] - mx_dp[k+1][j])

    answer = mx_dp[0][-1]
    
    return answer

 

1. A + B  또는 A - B로 추상화해서 생각하자.

•  해당 문제를 보고 연산자에 따라 A+B 또는 A-B로 생각해내는게 포인트이다. 
• A와 B 안에는 어떠한 연산자의 결과값이 있을지 모른다.
  • ((1 - 3) + 5)  또는  ((1 - (3 + 5)) - 8)  또는 (1 - 3)과 같은 결과값에서 어느게 올지 모르지만,
    이것들을 묶어서 A + B / A - B로 단편적으로 생각하면 된다. 
• 문제를 이렇게 풀기위해서는 DP 2차원 배열이 필요

 

 

2. 이제 이러한 관점으로 DP의 2차원 배열 (최대값, 최소값)을 만들어주면 된다. 

• 최대와 최소값을 구하는 이유는 다음과 같다.
  • 문제에서 원하는 최대값을 구하기 위함
  • 최대 값을 구하는 방법
    • + 연산자에서는 최대 DP + 최대 DP
    • - 연산자에서는 최대 DP - 최소 DP 
  • 위와 같은 이유 때문에 최대, 최소 DP 값이 필요하다. 

 

 

3. 2차원 DP 배열에서 인덱스의 의미 

• MAX DP [ i ] [ j ] 는 i ~ j 인덱스에서 최대값
• MIN DP [ i ] [ j ] 는 i ~ j 인덱스에서 최소값
• 예를들어 mx_dp[0][2] 는 0번째부터 2번째 인덱스까지의 최대값
• 해당 인덱스 값을 구하기 위하는 방법
  • [0][0] + [1][2]  또는 [0][1] + [2][2] 이 방법 뿐이다. 
  • 해당 결과값 중 최대 값을 [0][2] 인덱스에 넣으면 된다.

 

 

4. DP 배열 조건에 맞는 반복문 구성

숫자의 길이 4개 기준 예시 (A+B 또는 A-B)

1. 길이 2개 
[0][1]  :  [0][0]  [1][1] 
[1][2]  :  [1][1]  [2][2] 
[2][3]  :  [2][2]  [3][3]

2. 길이 3개 
[0][2]  :  [0][0]  [1][2]  or  [0][1]  [2][2]
[1][3]  :  [1][1]  [2][3]  or  [1][2]  [3][3]

3. 길이 4개 
[0][3]  :  [0][0]  [1][3]  or  [0][1]  [2][3]  or   [0][2]  [2][3]

• 위와 같은 조건에 충족하는 반복문을 만들면 된다.
  • 오른쪽 대각선 방향으로 채워나감
• 전체 길이를 만들어주는 반복문 
  • length 변수 (2 ~ n+1)
• 길이에 따라 인덱스 조절하는 반복문
  • i 변수 ( n - length + 1)
  • j 변수 ( i + length - 1)
• A 와 B의 경계를 나눠주는 반복문
  • k 변수 (i ~ j) 

n = 4 
for length in range(2, n+1):
    for i in range(n-length+1):
        j = i + length -1 
        for k in range(i,j):
            print(f"[{i}][{k}] ~ [{k+1}][{j}]", end=" ")
        print()
    print()

• 위에 작성했던 반복문 수도코드를 바탕으로 for 문 테스트 
  
  

 

5. 이제 구현만 하면된다. 

 

• 구현은 어렵지 않다. 
• 연산자, 숫자는 규칙적인 위치에 있으므로, 인덱스 홀/짝 기준으로 분리
• 주의 할 점으로는 DP는 항상 초기값 주의 !
• 덧셈일때는 그냥 더하면 되지만, 뺄셈일 때는 다르게 해야 함

 

 

시간 복잡도 O( N ^ 3) 

→  3중 반복문 부분에서 각각 O(N)

N의 최대 값이 100이므로 1,000,000 정도의 복잡도이므로 해당 풀이 문제 없음

 

---

📌  문제 코멘트 

DP는 인간적으로 간단하게 냈으면 좋겠다 ... 너무 어렵다 ㅠㅠ 

이 문제를 포스팅 하는 이유는 다음과 같다.

• 풀었던 DP 중에 가장 어려웠던 문제  (갱신 !! 이게 제일 어려움 ...) 
• 2차원 DP 배열로 이러한 문제 풀이
  1. 2차원 DP 배열이 특이한게 아니라, 이런 유형의 문제는 이렇게 푸는구나 하는 느낌
  2. 2차원 배열에서 인덱스가 의미하는 것
• 복잡한 조건에 따른 for문 순차적으로 구성
  • 실제 예시를 들어가며, 그 예시에 따라 for문을 구성해야 함 

---

📚  문제