[BOJ][🟡4][백준#02228] 구간 나누기

문제 출처

BAEKJOON Online Judge #2228

문제

N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다.

각 구간은 한 개 이상의 연속된 수들로 이루어진다. 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다. 정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다.

N개의 수들이 주어졌을 때, 답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 배열을 이루는 수들이 차례로 주어진다. 배열을 이루는 수들은 -32768 이상 32767 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

예제

입력

6 2
-1
3
1
2
4
-1

출력

9

My Sol

import sys
# sys.stdin = open('t.txt')
input = sys.stdin.readline

def foo(part, pe):
    global N, M, ans, ssum
    s = e = pe + 2

    if part == M:
        while s < N:
            if e <= N:
                ssum[part] = sarr[e] - sarr[s-1]
                ans = max(ans, sum(ssum))
                e += 1
            else:
                s += 1
                e = s
        return

    while s < N:
        if e <= N:
            ssum[part] = sarr[e] - sarr[s-1]
            foo(part+1, e)
            e += 1
        else:
            s += 1
            e = s


N, M = map(int, input().split())
arr = [int(input()) for _ in range(N)]
sarr = [0]*(N+1)
for i in range(1, N+1):
    sarr[i] = sarr[i-1] + arr[i-1]

ssum = [0]*(M+1)
ans = -1e7
foo(1, -1)
print(ans)

재귀와 투포인터를 이용해 지정된 개수의 구간마다의 합을 구해 ans에 최댓값을 매번 갱신하는 방식으로 문제를 풀었다.

결과

시간초과

아무래도 구간이 많아지면 sarr에도 값의 개수가 많아지고, 그만큼 sum하고 재귀 단계를 오가는 과정이 많아지다보니 시간 초과가 발생한 것 같다.

모범답안

출처

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
con = [[0]+[-1e9]*m for i in range(n+1)]
notcon = [[0]+[-1e9]*m for i in range(n+1)]

for i in range(1, n+1):
    num = int(input())
    for j in range(1, min(m, (i+1)//2)+1):
        notcon[i][j]=max(con[i-1][j], notcon[i-1][j])
        con[i][j]=max(con[i-1][j], notcon[i-1][j-1])+num
print(max(con[n][m], notcon[n][m]))

특정 idx까지 n개의 구간합을 구하고자 할 때, max(앞의 원소를 제외한 n-1개의 최대 구간합, 앞의 원소를 포함한 n개의 최대 구간합)+현재값을 적용했다고 한다. 어떻게 이런 발상을…. dp는 정말 어려운 것 같다.

j의 범위는 왜 range(1, min(m, (i+1)//2)+1)인걸까. 구간이 1개부터 가능한 구간의 개수를 따져야하기 때문인 것 같다. 구간의 개수 j는 m을 넘길 수 없고, 많아도 (i+1//2)을 넘길 수 없다. 때문에 이런 제약을 두지 않았을까.