[BOJ] Q2228 구간 나누기

[BOJ] Q2228 구간 나누기

Question

Language: Python

Difficulty: Gold 4

해당 문제의 핵심은 아래와 같은 점화식을 세우는 것이 중요하다

1. 마지막 index를 포함하지 않는 경우: f_n-1,m
2. 마지막 index를 포함하는 경우: max(f_k-2,m-1+prefix_sum[n]-prefix_sum[k-1])

Solution

from math import inf

def dfs(n,m):
    global dp
    #구간이 0 인경우 --> 가지는 구간합은 무조건 0이다.
    if m==0:
        return 0
    #인덱스를 벗어나는 경우
    if n<0 :
        return -inf

    if dp[n][m] == None:
        #마지막 index를 포함하지 않는 경우
        dp[n][m]=dfs(n-1,m)
        #m==1이라는 것은 구간이 1개이므로, 구간합을 이용해서 특정 구간이 가질 수 있는 최대합으로 설정한다.
        if m==1:
            dp[n][m]=max(dp[n][m],prefix_sum[n])
        #마지막 index을 포함하는 경우
        for k in range(n,0,-1):
            dp[n][m]=max(dp[n][m], dfs(k-2,m-1) + prefix_sum[n]-prefix_sum[k-1])

    return dp[n][m]

if __name__ == "__main__":
    N,M=map(int,input().split())
    dp=[[None]*(M+1) for _ in range(N)]
    prefix_sum=[int(input())]
    for _ in range(N-1):
        prefix_sum.append(prefix_sum[-1]+int(input()))

    print(dfs(N-1,M))