https://www.acmicpc.net/problem/2228
이 문제는 '한 칸 씩 진행하며 각 원소마다 구간에 포함 시킬 것인지 말 것인지를 결정하는 문제'로 해석해 볼 수 있다.
한 칸 단위로 진행하는 문제의 경우 ‘동일한 상태’라는 것을 정의하기 위한 요소로
- 지금까지 고려한 숫자의 위치
- 지금까지 선택한 구간의 수
- 마지막 숫자가 구간에 속했는지에 대한 여부
- 지금까지 얻은 합
이렇게 네 가지를 생각해볼 수 있다.
그 중에서
- 지금까지 고려한 숫자의 위치
- 지금까지 선택한 구간의 수
- 마지막 숫자가 구간에 속했는지에 대한 여부
가 정해졌을 때 '지금까지 얻은 합을 최대'로 하는 점화식을 세워보면 문제를 해결할 수 있다.
이 문제에 대한 풀이로, 한 칸씩 진행하며 각 원소마다 구간에 포함 시킨 경우와 그렇지 않은 경우로 나눠 최대 합을 구하는 방법을 설명해보려고 한다.
위에서 언급한 ‘동일한 상태’란?
ex) 5번째 원소까지 확인한 경우
case 1 ) [ 1 , 3 ] , 7 , [ 4 ] , 3 | ⇒ sum = 8
case 2) [ 1 ] , 3 , [ 7 ] , 4 , 3 | ⇒ sum = 8
case 1 의 경우에서는 [1, 2] 구간과 [4, 4] 구간 총 2개의 구간을 선택하여 합을 8만큼 얻게 되었고, 5번째 원소는 구간에 포함시키지 않았으며, 앞으로 6번째 위치 부터 어떤 원소를 구간에 추가할지를 고민해보려고하는 상황이고
case 2 의 경우에서는 [1, 1] 구간과 [3, 3] 구간 총 2개의 구간을 선택하여 합을 8만큼 얻게 되었고, 5번째 원소는 구간에 포함시키지 않았으며, 앞으로 6번째 위치 부터 원소를 구간에 추가할지 고민해보려고하는 상황이다.
이러한 상황에서 5번째 위치 이후로 구간에 추가 할 원소를 적절히 골라 선택한 총 구간의 개수가 정확히 m개가 되도록 하면서, 선택된 원소의 합이 최대가 되도록 만드려는 입장에서 봤을때
앞의 두 상황은 '동등한 상황'이다.
왜냐하면 앞에서 선택한 구간의 수는 정확히 2개로 일치하고, 얻은 합이 8로 일치하며, 지금까지 고려한 원소의 위치 역시 5로 일치하고, 마지막으로 5번째 원소를 두 경우 모두 구간에 포함시키지 않았기 때문에 6번째 원소에 미치는 ‘영향’이 정확히 동일할 것이기 때문이다.
여기서 ‘영향’이란?
만약 첫번째 경우에는 5번째 원소를 구간에 포함시켰고, 두번째 경우에는 5번째 원소를 구간에 포함시키지 않았다면, 6번째 원소를 구간에 포함시키려고 할 때, 전자의 경우 구간의 개수가 늘지 않게 되지만, 후자의 경우 6번째 원소가 새로운 구간의 시작이 되기 떼문에 구간의 개수가 하나 늘게 되므로, 각각의 경우가 6번째 원소에 미치는 영향이 다르다고 볼 수 있다.
즉, 이 문제에서 다음 4가지가 정확히 일치하는 경우 그 후의 입장에서 봤을 때 아예 ‘동일한 상황’이라 느끼게 된다는 것을 알 수 있다
- 지금까지 고려한 숫자의 위치
- 지금까지 선택한 구간의 수
- 마지막 숫자가 구간에 속했는지에 대한 여부
- 지금까지 얻은 합
따라서 이 문제를 다음과 같이 해석해 볼 수 있다.
지금까지 고려한 숫자의 위치와 선택한 구간의 수 그리고 마지막 숫자가 구간에 속했는지에 대한 상태가 모두 같다면, 얻은 합이 클수록 더 좋다.
그렇기 때문에 점화식을 다음과 같이 세울 수 있다.
dp[i][j][k] := i 번째 위치까지 고려하여 총 j 개의 구간을 선택했고, (i번째 원소가 마지막 구간에 속하지 않았다면 0, i번째 구간에 속했다면 1 이라 했을 때), 얻을 수 있는 최대 합
이 dp[i][j][k] 값을 구하기 위해서는 i 번째 숫자를 구간에 포함시킨 경우와 포함시키지 않은 경우로 나눠 각각 점화식을 세워야 한다.
case 1 ) i 번째 숫자를 구간에 포함시킨 경우
이 경우에는 다음 2가지 중에 더 좋은 값을 택해야 한다.
-
i 번째 숫자가 새로운 구간의 시작인 경우
이전 구간이랑 겹치지 않아야 하므로. i - 1 번째 숫자는 구간에 속하지 않는 상태여야 하며, 그때 까지 j - 1 개의 구간을 이미 선택했어야 비로소 i 번째 숫자를 포함해 j 개의 구간을 선택하게 된다
dp[i - 1][j - 1][0] + a[i]-
i 번째 숫자가 이미 j 번째 구간에 포함되어있는 경우
이 경우에도, 이전 구간이랑 겹치지 않아야 하므로 j번째 구간에 i - 1 번째 원소도 구간에 반드시 속해 있었어야 하며, 그 구간내에 i번째 숫자를 포함 해준다
dp[i - 1][j][1] + a[i]따라서 둘 중의 더 큰 값을 고르면 된다.
dp[i][j][1] = max(dp[i - 1][j - 1][0] + a[i], dp[i - 1][j][1] + a[i])case 2) i 번째 숫자를 구간에 포함시키지 않은 경우
이 경우에는 i - 1 번째 원소를 j 번째 구간에 포함시켰는지에 대한 여부가 크게 중요하지 않으므로, i - 1번째 원소를 j 번째 구간에 포함하지 않은 경우와, 포함한 경우 중 더 큰 값을 고르면 된다.
dp[i][j][1] = max(dp[i - 1][j][0], dp[i - 1][j][1])이어서 이 문제는 최대를 구하는 문제 이므로, 처음에 초기 조건을 제외한 나머지 위치에 전부 큰 음수 값을 적어주어 후에 점화식을 이용해 최대값을 구할 때의 계산이 용이해지도록 한다.
이 문제는 계산 도중 음수 값이 더해져 underflow가 발생할 수 있으므로, 이 문제에서 답이 될 수 있는 최솟값인 -3,276,800 을 초기값으로 설정하여 underflow 을 예방할 수 있다.
DP 에서 가장 중요한 것은 초기 조건이다. dp 배열에 올바른 값이 채워지기 위해서는 초기에 값을 잘 적어줘야 한다.
이 문제에서 필요로 하는 초기 조건은 선택한 구간의 개수가 0개인 경우를 설정하는 것이다.
0 에서 n 사이의 모든 위치 j 에 대해서 선택한 구간의 수는 0개이고, 해당 원소는 구간에서 사용하지 않았으며, 선택한 구간이 없으므로, 초기 합은 0이기 때문에 dp[i][0][0] = 0
정답 코드)
import sys
# 주의) 단, 선택한 구간끼리 겹처서는 안된다.
si = sys.stdin.readline
INT_MIN = -sys.maxsize # 다른 언어라면 underflow의 위험이 있을 수 있음
n, m = map(int, si().split())
arr = [0]
for _ in range(n):
arr.append(int(si()))
dp = [[[0 for _ in range(2)] for _ in range(m + 1)] for _ in range(n + 1)]
def preprocess():
for i in range(0, n + 1):
for j in range(0, m + 1):
for k in range(0, 2):
# 현재까지 사용한 괄호가 없고, i번째 원소도 구간에 포함시키지 않을 때
if j == 0 and k == 0:
dp[i][j][k] = 0
continue
dp[i][j][k] = INT_MIN
def find_max_sum():
for i in range(1, n + 1):
for j in range(1, m + 1):
for k in range(0, 2):
# i번째 숫자를 구간에 포함하지 않음 -> i-1 번째 원소가 j번째 구간에 포함되었는지, 포함되지 않았는지 중요하지 않음(영향을 받지 않음)
# i-1번째 선택까지의 합 중 큰 것을 선택
if k == 0:
dp[i][j][k] = max(dp[i - 1][j][0], dp[i - 1][j][1])
# i번째 숫자를 구간에 포함 -> i번째 숫자를 기존 구간에 포함시키는 경우의 수와 새로운 구간을 만든 경우의 수 중 큰 것을 고름
elif k == 1:
dp[i][j][k] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1]) + arr[i]
preprocess()
find_max_sum()
print(max(dp[n][m][0], dp[n][m][1]))