[Java] 백준 2228. 구간 나누기

📌 문제 링크 - https://www.acmicpc.net/problem/2228

 

 

---

 

 

 

 

 

 

문제

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

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

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

 

 

 

입력

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

 

 

 

출력

첫째 줄에 구간에 속한 수들의 총 합의 최댓값을 출력한다.

 

 

 

 

 

 

---

 

 

풀이

[예제]

{-1, 3, 1, 2, 4, -1}이 있을 때, {-1, 3, 1, 2, 4, -1}처럼 (3)과 (2, 4)로 구간을 나눴을 때 합이 9가 나오며 이것이 최댓값이다. 

 

 

max[n][m] : n 개의 수를 m 개의 구간으로 나눴을 때 구간에 속한 최댓값을 저장해 준다.

 

n 번째 원소가 포함이 안 되는 경우 max[n][m] = max[n-1][m]

n 번째 원소가 포함이 되는 경우 max[n][m] = Math.max(max[n][m], max[s - 2][m - 1] + sum[n] - sum[s - 1])

 

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/2228
public class Main_2228 {
    private static final int MIN = -3276800;
    private static int N, M;
    private static int[] sum; // 누적합


    public static void main(String[] args) throws IOException {
        init();

        int max = getMax();
        System.out.print(max);
    }//main


    private static int getMax() {
        int[][] max = new int[N+1][M+1];

        Arrays.fill(max[0], MIN);
        max[0][0] = 0;

        for(int n=1; n<=N; n++) {
            for(int m=1; m<=M; m++) {
                max[n][m] = max[n-1][m];
                for(int s=1; s<=n; s++) { // s 번째 원소부터 구간 시작
                    // 새로운 구간 만들기 가능
                    if(s >= 2) {
                        max[n][m] = Math.max(max[n][m], max[s - 2][m - 1] + sum[n] - sum[s - 1]);
                    }
                    // 구간이 하나
                    else if(s == 1 && m == 1) {
                        max[n][m] = Math.max(max[n][m], sum[n]);
                    }
                }
            }
        }

        return max[N][M];
    }//getMax


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 숫자 개수
        M = Integer.parseInt(st.nextToken()); // 구간 개수

        sum = new int[N+1]; // 누적합

        for(int i=1; i<=N; i++) {
            int num = Integer.parseInt(br.readLine());
            sum[i] = sum[i-1] + num;
        }

        br.close();
    }//init

}//class