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

문제

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

프로그래머스

 

 

너무 어렵다 ㅠㅠㅠ..

---

 

주요 아이디어

DP 형식으로 풀어야 한다 (그리디로는 최적값을 보장하지 않는다)

괄호를 어디 치느냐에 따라서 연산 결과가 달라지기 때문에, 각 경우를 모두 dp 배열에 저장해두어야 한다.

-> 각 구간별 연산의 최대값을 저장해두자

 

이 때!! 또 한 가지 중요한 것이 있다.

바로 '뺄셈'의 존재!

연산 기호가 덧셈일 때는 '연산자 위치 이전 최대값' + '연산자 위치 이후 최대값' 을 하면 되지만,

뺄셈일 경우에는 '연산자 위치 이전 최대값' - '연산자 위치 이후 최소값' 을 해야 최대값을 구할 수 있다.

 

주어진 예시를 통해 구체화해보자.

 

예제 1. 1 - 5 - 3

 [max_dp]

	0	1	2	3	4
0	1	x	-4	x	-1
1	x	-	x	x	x
2	x	x	5	x	2
3	x	x	x	-	x
4	x	x	x	x	3

max_dp[0][4] = max_dp[0][2] - max_dp[4][4], max_dp[0][0] - max_dp[2][4]

• max_dp[0][2] - min_dp[4][4] = -4-3 = -7
• max_dp[0][0] - min_dp[2][4] = 1-2 = -1

 

[min_dp]

	0	1	2	3	4
0	1	x	-4	x	-7
1	x	-	x	x	x
2	x	x	5	x	2
3	x	x	x	-	x
4	x	x	x	x	3

min_dp[0][4] = min_dp[0][2] - min_dp[4][4], min_dp[0][0] - min_dp[2][4]

• min_dp[0][2] - min_dp[4][4] = -4-3 = -7
• min_dp[0][0] - min_dp[2][4] = 1-2 = -1

 

 

예제 2. 1 - 3 + 5  - 8

 [max_dp]

	0	1	2	3	4	5	6
0	1	x	-2	x	3	x	1
1	x	-	x	x	x	x	x
2	x	x	3	x	8	x	0
3	x	x	x	+	x	x	x
4	x	x	x	x	5	x	-3
5	x	x	x	x	x	-	x
6	x	x	x	x	x	x	8

max_dp[0][4] = max_dp[0][2] + max_dp[4][4] , max_dp[0][0] - min_dp[2][4]

• max_dp[0][4] = max_dp[0][2] + max_dp[4][4] = -2 + 5 = 3
• max_dp[0][4] = max_dp[0][0] - min_dp[2][4] = 1 - 8 = -7

max_dp[2][6] = max_dp[2][4] - min_dp[6][6], max_dp[2][2] + max_dp[4][6]

• max_dp[2][6] = max_dp[2][4] - min_dp[6][6] = 8 - 8 = 0
• max_dp[2][6] = max_dp[2][2] + max_dp[4][6] = 3 - 3 = 0

max_dp[0][6] = max_dp[0][4] - min_dp[6][6], max_dp[0][0] - min_dp[2][6]

• max_dp[0][6] = max_dp[0][4] - min_dp[6][6] = 3 - 8 = -5
• max_dp[0][6] = max_dp[0][0] - min_dp[2][6] = 1 - 0 = 1

 

[min_dp]

	0	1	2	3	4	5	6
0	1	x	-2	x	-7	x	-15
1	x	-	x	x	x	x	x
2	x	x	3	x	8	x	0
3	x	x	x	+	x	x	x
4	x	x	x	x	5	x	-3
5	x	x	x	x	x	-	x
6	x	x	x	x	x	x	8

min_dp[0][4] = min_dp[0][2] + min_dp[4][4] , min_dp[0][0] - max_dp[2][4]

• min_dp[0][4] = min_dp[0][2] + min_dp[4][4] = -2 + 5 = 3
• min_dp[0][4] = min_dp[0][0] - max_dp[2][4] = 1 - 8 = -7

min_dp [2][6] = min_dp [2][4] - max_dp[6][6], min_dp [2][2] + min_dp [4][6]

• min_dp [2][6] = min_dp [2][4] - max_dp[6][6] = 8 - 8 = 0
• min_dp [2][6] = min_dp [2][2] + min_dp [4][6] = 3 - 3 = 0

min_dp[0][6] = min_dp[0][4] - max_dp[6][6], min_dp[0][0] - max_dp[2][6]

• min_dp [0][6] = min_dp[0][4] - max_dp[6][6]  = -7 - 8 = -15
• min_dp [0][6] = min_dp[0][0] - max_dp[2][6]  = 1 -0 = 1

 

예제 3. 5 - 3 + 1 + 2 - 4

 [max_dp]

	0	1	2	3	4	5	6	7	8
0	5	x	2	x	3	x	5	x	3
1	x	-	x	x	x	x	x	x	x
2	x	x	3	x	4	x	6	x	2
3	x	x	x	+	x	x	x	x	x
4	x	x	x	x	1	x	3	x	-1
5	x	x	x	x	x	+	x	x	x
6	x	x	x	x	x	x	2	x	-2
7	x	x	x	x	x	x	x	-	x
8	x	x	x	x	x	x	x	x	4

max_dp[0][4] = max_dp[0][2] + max_dp[4][4] , max_dp[0][0] - min_dp[2][4]

• max_dp[0][4] = max_dp[0][2] + max_dp[4][4] = 2 + 1 = 3
• max_dp[0][4] = max_dp[0][0] - min_dp[2][4] = 5 - 8 = -3

max_dp[2][6] = max_dp[2][2] + max_dp[4][6], max_dp[2][4] + max_dp[6][6]

• max_dp[2][6] = max_dp[2][2] + max_dp[4][6] = 3 + 3 = 6
• max_dp[2][6] = max_dp[2][4] + max_dp[6][6] = 4 + 2 = 6

max_dp[4][8] = max_dp[4][4] + max_dp[6][8], max_dp[4][6] - min_dp[8][8]

• max_dp[4][8] = max_dp[4][4] + max_dp[6][8] = 1 + (-2) = -1
• max_dp[4][8] = max_dp[4][6] - min_dp[8][8] = 3 - 4 = -1

max_dp[2][8] = max_dp[2][2] + max_dp[4][8], max_dp[2][6] - min_dp[8][8]

• max_dp[2][8] = max_dp[2][2] + max_dp[4][8] = 3 + (-1) = 2
• max_dp[2][8] = max_dp[2][6] - min_dp[8][8] = 6 - 4 = 2

 

max_dp[0][8] = max_dp[0][0] - min_dp[2][8], max_dp[0][6] - min_dp[8][8]

• max_dp[0][8] = max_dp[0][0] - min_dp[2][8] = 5 - 2 = 3
• max_dp[0][8] = max_dp[0][6] - min_dp[8][8] = 5 - 4 = 1

 

[min_dp]

	0	1	2	3	4	5	6	7	8
0	5	x	2	x	-3	x		x
1	x	-	x	x	x	x	x	x	x
2	x	x	3	x	4	x	6	x	2
3	x	x	x	+	x	x	x	x	x
4	x	x	x	x	1	x	3	x	-1
5	x	x	x	x	x	+	x	x	x
6	x	x	x	x	x	x	2	x	-2
7	x	x	x	x	x	x	x	-	x
8	x	x	x	x	x	x	x	x	4

min_dp[0][4] = min_dp[0][2] + min_dp[4][4] , min_dp[0][0] - max_dp[2][4]

• min_dp[0][4] = min_dp[0][2] + min_dp[4][4] = 2 + 1 = 3
• min_dp[0][4] = min_dp[0][0] - max_dp[2][4] = 5 - 8 = -3

min_dp [2][6] = min_dp [2][2] + min_dp [4][6], min_dp [2][4] + min_dp [6][6]

• min_dp [2][6] = min_dp [2][2] + min_dp [4][6] = 3 + 3 = 6
• min_dp [2][6] = min_dp [2][4] + min_dp [6][6] = 4 + 2 = 6

min_dp [4][8] = min_dp [4][4] + min_dp [6][8], min_dp [4][6] - max_dp [8][8]

• min_dp [4][8] = min_dp [4][4] + min_dp [6][8]  = 1 + (-2) = -1
• min_dp [4][8] = min_dp [4][6] - max_dp [8][8] = 3-4 = -1

min_dp [2][8] = min_dp [2][2] + min_dp [4][8], min_dp [2][6] - max_dp [8][8]

• min_dp [2][8] = min_dp [2][2] + min_dp [4][8] = 3 + (-1) = 2
• min_dp [2][8] = min_dp [2][6] - max_dp [8][8] = 6 - 4 =2

 

따라서 다음과 같이 배열을 할당하고 코드를 작성한다.

• nums = 숫자 배열
• ops = 연산자 배열
• max_dp = 구간별 최대값
  • ex. max_dp[0][4] : 0~4 구간까지의 최대값
• min_dp = 구간별 최소값
  • ex. min_dp[0][4] : 0~4 구간까지의 최소값

 

---

 

코드 구현 (Python 3)

 

def solution(arr):
    nums = [int(x) for x in arr[::2]] # 숫자만 저장
    ops = [x for x in arr[1::2]] # 연산자만 저장
    
    max_dp = [[0 for _ in range(len(arr))] for _ in range(len(arr))]
    min_dp = [[1001 for _ in range(len(arr))] for _ in range(len(arr))]
    
    for idx, num in enumerate(nums):
        max_dp[idx][idx] = num
        min_dp[idx][idx] = num
    
    # 각 구간마다의 최대값, 최소값 구하기 구하기
    for interval in range(1, len(nums)):
        for i in range(len(nums)):
            j = i + interval
            if j >= len(nums):
                continue
                
            max_c = []; min_c = []
            
            for k in range(i+1, j+1):
                # 연산자가 '+'인 경우 = 최대값 + 최대값
                if ops[k-1] == '+':
                    max_c.append(max_dp[i][k-1] + max_dp[k][j])
                    min_c.append(min_dp[i][k-1] + min_dp[k][j])
                    
                # 연산자가 '-'인 경우 = 최대값 - 최소값
                elif ops[k-1] == '-':
                    max_c.append(max_dp[i][k-1] - min_dp[k][j])
                    min_c.append(min_dp[i][k-1] - max_dp[k][j])
                    
            max_dp[i][j] = max(max_c); min_dp[i][j] = min(min_c)
    
    
    return max_dp[0][len(nums)-1]

 

 

 

 

제출 결과

---

 

참고 자료

[프로그래머스] 사칙연산 Python 파이썬 해설 (Level 4) - 이도훈