[백준] 2228: 구간 나누기 - JAVA

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

 

풀이

n개의 수로 이루어진 배열에서 m개의 구간을 선택해 각 구간들의 합의 최댓값을 구하는 문제.

 

단, 구간 사이에는 최소 1의 간격이 있어야한다.

 

dp 이차원 배열을 만들었다. `[수의 번호][구간의 개수]`로 구성했다.

for (int k = i; k > 0; k--) {
    if (k - 2 >= 0) {
        dp[i][j] = Math.max(dp[i][j], dp[k - 2][j - 1] + sum[i] - sum[k - 1]);
    } else if (k == 1 && j == 1) {
        dp[i][j] = Math.max(dp[i][j], sum[i]);
    }
}

 

k번째 원소를 보면서 k번째 원소가 포함되는 경우, 포함되지 않는 경우를 나눠 최댓값을 갱신했다.

 

---

 

메모리: 14388KB
시간: 144ms
언어: Java 11

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

public 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[] sum = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            sum[i] = Integer.parseInt(br.readLine()) + sum[i - 1];
        }

        int[][] dp = new int[n + 1][m + 1];
        Arrays.fill(dp[0], -32768 * 101);
        dp[0][0] = 0;

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = i; k > 0; k--) {
                    if (k - 2 >= 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[k - 2][j - 1] + sum[i] - sum[k - 1]);
                    } else if (k == 1 && j == 1) {
                        dp[i][j] = Math.max(dp[i][j], sum[i]);
                    }
                }
            }
        }

        System.out.println(dp[n][m]);
    }

}