[백준] 구간 나누기

https://www.acmicpc.net/problem/2228

2228번: 구간 나누기

DP를 활용하여 해결하였습니다. 이전에 같은 문제를 풀었던 적이 있는데도 한참을 헤매서 간신히 풀었습니다.

DP에서 가장 중요한 두가지는 초기 조건과 점화식입니다. 먼저, 점화식은 다음과 같습니다.

 

DP[k][i][0] -> k번째 구간에 i번째 숫자를 포함시키지 않는 경우, 이와 같은 경우에는 현재 숫자가 포함이 되지 않습니다. 그러므로 DP[k][i - 1][0], DP[k][i - 1][1] 이전 숫자를 포함하거나 하지 않은 경우와 상관없이 둘 중에 더 큰 값을 택하면 됩니다.

 

DP[k][i][1] -> k번째 구간에 i번째 숫자를 포함시키는 경우, DP[k][i - 1][1], DP[k - 1][i - 1][0] 둘 중 더 큰 값을 택해야하는데 i - 1까지 선택되어 현재 숫자까지 K번째 구간이 이어지는 경우와 이전 숫자를 택하지 않아여 k - 1번째 구간까지 선택된 경우 중 더 큰 값을 택해주면 됩니다.

 

초기 조건의 경우에는 기본적으로 최대값을 구해야하므로 -INT_MAX로 초기화 해주고 0번째 구간에 i번째 숫자를 고르지 않는 경우에는 기본적으로 0이 되므로 0으로 초기화해줍니다.

 

import sys
INT_MAX = sys.maxsize
sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

nums = [0]

for _ in range(n):
    num = int(input())

    nums.append(num)

dp = [
    [[-INT_MAX] * 2
     for _ in range(n + 1)]
    for __ in range(m + 1)
]

for i in range(n + 1):
    dp[0][i][0] = 0

for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[j][i][1] = max(dp[j][i - 1][1], dp[j - 1][i - 1][0]) + nums[i]

        dp[j][i][0] = max(dp[j][i - 1][0], dp[j][i - 1][1])


print(max(dp[m][n][0], dp[m][n][1]))