백준 2228[자바] java 구간 나누기

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

2228번: 구간 나누기

▶문제

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

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

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

---

▶입력

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

---

▶출력

첫째 줄에 답을 출력한다.

---

▶해설

조건을 먼저 살펴보겠습니다.

1. 각 구간은 한 개 이상의 연속된 구간 -> 1개를 선택해도 무방하다. 하지만 여러 개일 경우 붙어 있는 수여야한다. 

2. 서로 다른 두 구간끼리는 겹쳐 있거나 인접해서는 안된다 -> 겹치지 않고, 중간에 하나의 간격이 있어야 한다.

3. 정확히 M개의 구간이 있어야 한다. -> m=2 개라면 2 개의 구간이 있어야 한다.

 

DP문제입니다.

 

먼저 N개의 수와 M개의 구간을 나눌 배열 dp[n+1][m+1]을 선언합니다. 

 

n을 키워 나가며, 해당 n을 구간에 포함시키지 않는다면 dp[n][m] = dp[n-1][m]이라고 할 수 있습니다.

 

하지만 n을 포함한다면, 겹쳐있거나 인접해서는 안된다. 조건으로 dp[n][m]와 dp[n-2][j-1]+sum[n]-sum[n-2]를 비교해서 더 큰 수를 넣어줍니다. 

dp[i][j] = Math.max(dp[i][j], dp[k][j-1]+sum[i]-sum[k+1]);

(단 m=1인 경우는 n까지의 합을 넣어주면 됩니다.)

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));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int [] arr = new int[n+1];
        int [] sum = new int[n+1];
        int [][] dp = new int[n+1][m+1];

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

        dp[1][1] = arr[1];
        for(int i=2; i<=n; i++){
            for(int j=1; j<=m; j++){
                dp[i][j] = dp[i-1][j];

                int min=0;
                if(j==1){
                    min=-1;
                }

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

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

    }
}