[BaekJoon] 2228 구간 나누기 (Java)

1.  문제 링크

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

2.  문제

요약

• N개의 수로 이루어진 다음의 조건들을 만족하며 1차원 배열에서 M개의 구간을 선택해 구간에 속한 수들의 총 합이 최대가 되도록 하려 합니다.
  1. 각 구간은 한 개 이상의 연속된 수들로 이루어져있습니다.
  2. 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안됩니다.
  3. 정확히 M개의 구간이 있어야 합니다.
• N개의 수들이 주어졌을 때 답을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 N과 1보다 크거나 같고 ⌈(N/2)⌉보다 작거나 같은 M이 주어지며 두 번째 줄부터 N개의 줄에 배열을 이루는 수가 차례대로 주어집니다. 배열을 이루는 수들은 -32768 이상 32767 이하의 정수입니다.
• 출력: 첫 번째 줄에 구간에 속한 수들의 총 합의 최댓값을 출력합니다.

3.  소스코드

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

public class Main {
    static int N, M;
    static int[] nums;
    static int[][][] dp;
    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        nums = new int[N + 1];
        dp = new int[N + 1][M + 1][2];
        for(int num = 0; num <= N; num++) {
            for(int partition = 0; partition <= M; partition++)
                Arrays.fill(dp[num][partition], Integer.MIN_VALUE);
        }

        for(int idx = 1; idx <= N; idx++)
            nums[idx] = scanner.nextInt();
    }

    static void solution() {
        dp[0][0][1] = dp[0][0][0] = 0;

        for(int num = 1; num <= N; num++) {
            for(int partition = 0; partition <= Math.min(M, num / 2); partition++)
                dp[num][partition][0] = Math.max(dp[num - 1][partition][1], dp[num - 1][partition][0]);
            
            for(int partition = 1; partition <= Math.min(M, (num + 1) / 2); partition++)
                dp[num][partition][1] = Math.max(dp[num - 1][partition - 1][0], dp[num - 1][partition][1]) + nums[num];
        }

        System.out.println(Math.max(dp[N][M][0], dp[N][M][1]));
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 3차원 배열 dp를 생성합니다. dp 배열이 나타내는 바는 다음과 같습니다.
  • dp[N][M][0] : N개의 수에서 N번째 수를 포함하지 않고 M개의 구간을 이용하여 합하였을 때의 최댓값
  • dp[N][M][1] : N개의 수에서 N번째 수를 포함하고 M개의 구간을 이용하여 합하였을 때의 최댓값
• dp[0][0]일 때에는 수도 없고 나눌 구간도 없으므로 dp[0][0][0], dp[0][0][1]은 0으로 값을 초기화합니다.
• 첫 번째 수부터 N번째 수까지 순회하면서 dp 배열을 채워나갑니다.
  • 우선 현재 수를 포함하지 않는 경우부터 구합니다.
    • N개의 수 중 N번째 수를 포함하지 않으므로 만들 수 있는 최대 구간 개수는 N / 2가 될 것입니다.
      • 예를 들어, N이 2일 때를 생각해보면 N번째 수를 포함하지 않으므로 하나의 수만으로 구간을 나누기 때문에 하나의 구간만 만들 수 있을 것입니다.
      • N이 3일 때를 생각해보면 N번째 수를 포함하지 않으므로 총 2개의 수를 이용하여 구간을 나누는데, 두 구간이 인접할 수 없으므로 하나의 구간만 만들 수 있을 것입니다.
    • 그러므로 M과 N / 2 중 작은 수를 partition이라고 하면 0부터 partition까지의 개수로 구간을 나눠보면서 그 때의 dp 배열을 채웁니다.
      • N번째 수를 선택하지 않기 때문에 N - 1번째 수를 골라도, 고르지 않아도 되므로 N - 1번째 수까지 현재 나누려는 구간의 개수로 나눴을 때의 최댓값을 구합니다.
      • dp[N][partition][0] = max(dp[N - 1][partition][0], dp[N - 1][partition][1])
  • 현재 수를 포함하는 경우를 구합니다.
    • N개의 수 중 N번째 수를 포함하므로 만들 수 있는 최대 구간 개수는 (N + 1) / 2가 될 것입니다.
      • 예를 들어, N이 2일 때를 생각해보면 N번째 수를 포함하므로 N번째 수는 하나의 구간을 형성할텐데, 두 구간이 인접할 수 없으므로 하나의 구간만 만들 수 있을 것입니다.
      • N이 3일 때를 생각해보면 N번째 수를 포함하므로 첫 번째 수와 세 번째 수를 각각 구간으로 잡으면 두 개의 구간을 만들 수 있을 것입니다.
    • 그러므로 M과 (N + 1) / 2 중 작은 수를 partition이라고 하면 0부터 partition까지의 개수로 구간을 나눠보면서 그 때의 dp 배열을 채웁니다.
      • N번째 수를 선택하기 때문에 N - 1번째 수를 고르지 않고 (현재 나누려는 구간의 개수 - 1)개의 구간으로 나눈 경우와, N - 1번째 수를 포함시켜 현재 나누려는 구간의 개수로 구간을 나누고 N - 1번째 수가 속한 구간에 N번째 수가 들어가는 경우가 있습니다. 그러므로 점화식은 아래와 같습니다.
      • dp[N][partition][1] = max(dp[N - 1][partition - 1][0], dp[N - 1][partition][1]) + (N번째 수)
• 위와 같은 방식으로 dp 배열을 모두 채웠다면, dp[N][M][0]과 dp[N][M][1] 중 더 큰 값이 답이 되게 됩니다.