문제 링크
생각의 흐름
- 문제에 대한 이해
- DP 문제 인식
- DP 구상
- 코드로 구현
<문제 파악>
문제의 이름은 사칙연산이지만 문제는 '+' 와 '-' 로 이루어진 더하기 빼기 문제이다. 식의 최대값이 되도록 '-'가 영향을 미치는 부분을 찾아낸다고 생각하면 이해가 빠르다. 문제에 대한 이해는 빠르게 되어도 어떻게 풀어야 할지 감이 잘 잡히지 않았다.
<DP 문제 인식>
이 문제가 DP인지 빠르게 눈치채는 것이 중요하다. 바로 눈치채기가 쉽지는 않은 문제였다. 하지만 그 전에 계산했던 최대 최소를 이용하여 최대 최소를 구해야 하기 때문에 DP 문제로 인식할 수 있었다.
<DP 구상>
더하기와 빼기로 이루어진 식의 최대를 구하려면 2가지 경우로 나뉜다.
- (최대) + (최대)
- (최대) - (최소)
이렇게 되면 뺄셈이 등장할 때 (최소)도 구해야한다. 그럼 최소를 구하는 방법 2가지도 생각해보자.- (최소) + (최소)
- (최소) - (최대)
하나의 식이 있다고 가정하면
(a) + (b) - (c) + (d) + (e) - ...
어느 구간의 길이를 정하고 구간의 시작점과 끝점을 잡고 그 안에서도 기준점을 처음부터 끝까지 옮기며 기준점을 기준으로 왼쪽과 오른쪽의 (최대) (최소)를 구하며 DP를 구성한다.
<코드로 구현하기>
포인트
- DP 구상 자체가 포인트인 문제...
def solution(arr):
nums = []
op = []
for i in arr:
if i != '+' and i!='-':
nums.append(int(i))
else:
op.append(i)
N = len(nums)
dp_min = [[float('inf')] * N for _ in range(N)]
dp_max = [[float('-inf')] * N for _ in range(N)]
for length in range(N):
for start in range(N-length):
end = start+length
if start == end:
dp_min[start][end] = dp_max[start][end] = nums[start]
continue
for mid in range(start,end):
if op[mid] == '+':
dp_min[start][end] = min(dp_min[start][mid] + dp_min[mid+1][end], dp_min[start][end])
dp_max[start][end] = max(dp_max[start][mid] + dp_max[mid+1][end], dp_max[start][end])
elif op[mid] == '-':
dp_min[start][end] = min(dp_min[start][mid] - dp_max[mid+1][end], dp_min[start][end])
dp_max[start][end] = max(dp_max[start][mid] - dp_min[mid+1][end], dp_max[start][end])
print(dp_max)
return dp_max[0][-1]
다른 사람의 풀이
다른 사람의 풀이에서 이해하기 쉬운 코드를 발견하여 읽어보고 이해한 것을 아래에 적어 놓았다.
def solution(arr):
arrs = ''.join(arr).split('-')
val0 = sum(list(map(int, arrs[0].split('+'))))
if len(arrs) == 1:
return val0
min_val = 0
max_val = 0
for arr in arrs[:0:-1]:
x = list(map(int, arr.split('+')))
_min_val = -(sum(x))
_max_val = sum(x[1:]) - x[0]
min_val, max_val = min(_min_val + min_val, _min_val - max_val), max(_max_val + max_val, _min_val - min_val)
return val0 + max_val
'-'를 기준으로 문자열을 나눈다. '-'를 기준으로 나눴기 때문에 '-' 이후의 첫 수는 무조건 음수이고, 그 이후의 수는 선택적이다.
그러므로 '-' 이후 한 묶음의 최소(_min_val)는 그 한 묶음의 전체 합의 음수이다. 최대(_max_val)는 한 묶음에서 첫 수만 음수이고 나머지는 양수로 취급한 것이다.
그럼 이제 식의 최대 최소를 구하는 방법을 이용하면 된다.
최대 구하기
- (최대) + (최대)
- (최대) - (최소)
최소 구하기
- (최소) + (최소)
- (최소) - (최대)
후기
사실 비슷한 문제가 나와도 제대로 풀어낼 자신이 없다. 이해는 되지만 몸에 익숙해지지 않는 문제다. 규칙을 찾아 그 전의 결과를 이용하여 다음값을 찾아가는 DP는 많이 경험해서 감이라도 잡히는데 이런 DP는 처음이었다.
수학식에 대한 이해, DP의 새로운 시각, DP 구상의 실력 모두 들어간 좋은 문제라고 생각한다. 나에겐 아직 어렵다...
