[백준] 2228번: 구간 나누기

2228번: 구간 나누기

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1

6 2
-1
3
1
2
4
-1

예제 출력 1

9

 

문제 번역이 그렇게 매끄럽지 못해서 이해하는 데 시간이 좀 걸렸던 문제입니다. 예제에서 선택하는 구간은 [3] 과, [2, 4] 입니다.

선택해야 하는 구간의 갯수가 주어지고, 그 갯수에 맞게 구간을 선택해야 하는 문제이기 때문에 좀 까다롭게 느껴질 수 있습니다.

 

여기서 dp 배열은 dp[n][m]으로 잡았는데요. 1부터 n 인덱스까지의 1차원 배열에서 m개의 구간을 선택했을 때 합의 최댓값을 의미합니다.

구간의 갯수를 인덱스로 잡기로 했기 때문에 다른 문제들을 풀 때처럼, "dp[i][j] : i부터 j까지" 이런 식으로는 풀이를 할 수 없습니다. 그래서 이번 문제에서는 누적합을 이용해서 구간을 계산해줬습니다.

 

풀이는 주석으로 대체합니다.

#include <iostream>
using namespace std;

#define MIN -3276800;

int arr[101];
int dp[101][51];

int calculate(int n, int m) {
    if (m == 0) return 0;
    if (n <= 0) return MIN;
    if (dp[n][m] != -1) return dp[n][m];

    int sum = 0;
    // 3: n번째 인덱스가 구간에 포함되지 않는 경우. 재귀이기 때문에 그 이전의 모든 경우의 수가 계산된다.
    dp[n][m] = calculate(n - 1, m);
    for (int i = n; i > 0; i--) {
    	// 1: 누적합을 이용해서 1개의 구간을 구한다. (i부터 n까지의 구간)
        sum += arr[i];
        // 2: 인접하지 않는 범위에서 m - 1개의 구간의 합의 최댓값을 구한다.
        int tmp = calculate(i - 2, m - 1) + sum;
        if (tmp > dp[n][m]) {
            dp[n][m] = tmp;
        } 
    }

    return dp[n][m];
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        for (int j = 1; j <= n / 2; j++) {
            dp[i][j] = -1;
        }
    }

    cout << calculate(n, m) << '\n';

    return 0;
}