프로그래머스 사칙연산(DP) 풀이 + 비슷한 문제 추천

프로그래머스 사칙연산

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

프로그래머스

 

문제는 위의 링크에서 확인할 수 있다.

알고리즘 유형

알고리즘 유형은 DP로, 최댓값과 최솟값을 저장하는 DP를 따로 관리한다.

연산자가 "+"이면 최대+최대, 최소+최소, 연산자가 "-"이면 최대-최소, 최소-최대로 DP 테이블을 갱신한다.

문제 해결

1. 입력데이터(arr)에서 숫자와 연산자를 분리하여 저장, 최대DP, 최소DP초기화

2. 부분배열 설정: 두 개의 숫자를 연산해야하므로, 부분배열의 최소 크기는 2, 최대 크기는 arr 의 크기이다.

3. 부분배열의 시작점 및 끝점 설정: 부분 배열의 시작점 i부터 끝점 j를 설정한다. 이 때, j는 i+부분배열의 크기이다.

4. 연산자: 연산자는 부분배열 i부터 j 의 범위 이내에 있는 연산자를 가져온다. 

5. 점화식: 연산자에 따라 DP 테이블을 갱신한다.

    5-1) 덧셈 연산인 경우: 최대 DP 테이블은 최댓값+최댓값, 최소 DP 테이블은 최솟값+최솟값으로 갱신

    5-2) 뺄셈 연산인 경우: 최대 DP 테이블은 최댓값-최솟값, 최소 DP 테이블은 최댓값-최솟값으로 갱신

 

코드 작성

1. 입력데이터(arr)에서 숫자와 연산자를 분리하여 저장, 최대DP, 최소DP초기화

INF = 1e9
nums = [int(arr[i]) for i in range(0, len(arr), 2)] # 숫자
operators = [arr[i] for i in range(1, len(arr) - 1, 2] # 연산자
N = len(nums)

min_dp = [[INF] * N for _ in range(N)] # 최소DP
max_dp = [[-INF] * N for _ in range(N)] # 최대DP

# 자기 자신의 값
for i in range(N):
    min_dp[i][i] = max_dp[i][i] = nums[i]

 

 

2. 부분배열 설정

range가 1부터 시작하는 부분이 헷갈릴 수 있는데, 부분 배열의 크기라고 이해하면 된다. 

size가 1일땐 i를 0부터 1까지 가져오고, 1부터 2까지 가져오고, N-1부터 N까지 가져오고, size가 2일땐 0부터 2까지, 2부터 4까지, N-2부터 가져온다. 계속해서 부분배열의 크기를 키워서 최종적으로 전체 배열까지 도달한다.

for size in range(1, N) # 계산할 부분배열의 크기는 숫자 2개 -> 3개 -> ... -> N개 까지

 

 

3. 부분배열의 시작점 및 끝점 설정

0부터 N까지 순회하며 size 크기의 부분배열을 가져온다. 따라서 부분배열의 시작점이 i라면 끝점은 i + size 이고, j가 전체 배열의 크기를 넘지 않도록 i를 조절해준다. 예를 들면, N이 10이고 size가 2라면 마지막 부분배열은 인덱스 7, 8, 9를 가져와야 한다. 따라서  range(N-size)를 하여 i의 값을 0부터 7까지, j의 값을 2부터 9까지 가져와준다.

for i in range(N - size): #시작점
	j = i + size # 끝점

 

 

4. 연산자

부분배열 i부터 j 의 범위 이내에 있는 연산자를 가져온다. 

부분배열, 숫자, 연산자

 

for k in range(i, j): # 연산자 위치는 부분배열 i와 j 사이

 

 

5. 점화식

연산자에 따라 DP 테이블을 갱신한다.

부분배열 내의 연산자를 순회하며 DP 테이블을 갱신하며, 연산자를 기준으로 부분배열을 또 다시 쪼개어 최대/최솟값을 가져온다. 연산자 k 왼쪽의 값 + 연산자 + 연산자 k 오른 쪽의 값을 계산하며 테이블을 갱신한다.

if operators[k] == '+': # 덧셈 연산인 경우
	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]) # 최소 - 최대

 

 

6. 결과값 리턴

전체 배열을 계산한 최댓값을 리턴해야하므로, 최댓값을 저장한 DP 테이블 max_dp에서 0부터 N까지 전체 배열을 계산한 값 max_dp[0][N-1](또는 max_dp[0][-1]) 의 값을 가져온다

return max_dp[0][-1]

 

 

전체 코드

INF = 1e9
def solution(arr):
    nums = [int(arr[i]) for i in range(0, len(arr), 2)]
    operators = [arr[i] for i in range(1, len(arr)-1, 2)]
    N = len(nums)
    
    min_dp = [[INF] * N for i in range(N)]
    max_dp = [[-INF] * N for i in range(N)]
    
    for i in range(N):
        min_dp[i][i] = max_dp[i][i] = nums[i]
        
    for size in range(1, N): # 부분배열의 크기
        for i in range(N - size): # 시작점 
            j = i + size # 끝점
            for k in range(i, j): # 연산자 위치
                if operators[k] == "+": # 덧셈 연산
                    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][-1]

 

 

비슷한 문제들

아래는 방금 풀이한 문제와 유사한 유형의 문제들이다. ChatGPT한테 추천해달라고 하면 잘 해준다.

아래의 문제 중 LeetCode241 - Different Ways to Add Parentheses는 지금 풀이한 사칙연산과 매우 비슷한 문제이므로 꼭 다시 풀어볼 것!

번호	문제 이름	난이도	유형
1	백준 2504 - 괄호의 값	⭐⭐⭐	DP, Stack
2	백준 15486 - 퇴사 2	⭐⭐⭐	DP, 최적화
3	백준 11049 - 행렬 곱셈 순서	⭐⭐⭐⭐	DP, 연산 최적화
4	LeetCode 312 - Burst Balloons	⭐⭐⭐⭐	DP, 구간 최적화
5	백준 1912 - 연속합	⭐⭐	DP, 누적합
6	LeetCode 241 - Different Ways to Add Parentheses	⭐⭐⭐	DP, 괄호 배치