[Java] 2228 구간 나누기

문제

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

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

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

입력

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

출력

첫째 줄에 구간에 속한 수들의 총 합의 최댓값을 출력한다.
 
문제 링크 : 구간 나누기

---

설명

초기값 지정을 잘못해줘서 2시간 더 헤맨 문제다.
4%에서 틀렸습니다가 나온다면 99% dp 초기값 설정 문제라고 생각한다.
 
나는 음수끼리의 최대 합을 생각하지 못하고 최대 음수 값에서 -1 해준 -32769로 지정해 놨었는데 음수끼리의 누적합에서 초기값을 넘을 수 있다는 것을 뒤늦게 알았다.
 
혹시 이 말이 이해가 안된다면 아래 예시를 보자.
4 2
-32768
-32768
-10000
-32222
 
이 예시일때 누적합 배열에는 아래와 같이 저장된다.

 
그런데 현재 dp 초기값이 -32769 이므로 이 값은 누적합 보다 더 큰 값이 된다.
이런 상태로는 제대로된 결과값을 얻을 수 없게 된다. (결국 초기값이 제일 클 것이기 때문에.)
 
그래서 나는 -3276900 으로 잡아줬다. 딱히 의미는 없고 n이 최대가 100이여서 3백만으로 해줬다.

문제는 간단하다. 한개 이상의 연속된 수를 M개의 구간으로 나누어서 구간 수를 다 더했을 때 최댓값을 구하면 된다.

dp[i][j] = 각 구간에서 j번째 배열일 때 얻을 수 있는 최댓값
 
[i-1][k-2] 는 전 구간에서의 최댓값이다. -2를 한 이유는 인접한 경우는 안된다고 문제에 설명되어있으므로 인접하지 않은 배열을 선택하기 위해 -2 를 해준다.

 

코드

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken());
        int[][] dp = new int[m + 1][n + 1];
        int[] sum = new int[n + 1]; // 누적합 배열

        for (int i = 1; i <= n; i++){
            sum[i] = Integer.parseInt(br.readLine()) + sum[i -1];
        }
        for (int i = 1; i <= m; i++) dp[i][0] = -3276900;

        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                dp[i][j] = dp[i][j -1];
                for (int k = 1; k <= j; k++){
                    if (k >= 2){ // 구간을 나눌 수 있을 경우
                        dp[i][j] = Math.max(dp[i -1][k -2] + sum[j] - sum[k -1], dp[i][j]);
                    }
                    else if (k == 1 && i == 1) dp[i][j] = Math.max(dp[i][j], sum[j]);
                }
            }
        }
        System.out.println(dp[m][n]);
    }
}

 
 
초기값 틀린줄 모르고 틀린 곳도 없는데 여기저기 수정했다.