백준 2228 구간 나누기 (Java)

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

 

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

public class Main {
    public static void main(String[] args) throws IOException {


        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int n = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());


        int[] prefix = new int[n+1];
        int[][] dp = new int[n+1][m+1];         //dp[i][j]: i번째 숫자까지 j개의 부분합으로 나눴을 때 최대 구간합

        for(int i = 0; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = -32768 * 101;
            }
        }

        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + Integer.parseInt(reader.readLine());
        }

        dp[1][1] = prefix[1];

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

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


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

    }
}

1. 문제

 

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

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

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

입력

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

출력

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

2. 풀이

DP 문제이다. dp[i][j]를 다음과 같이 정의해보자.

 

• dp[i][j]: i 번째 숫자까지 j 개의 구간합으로 나눴을 때의 최대 부분합

 

 

i개까지의 숫자로 j 개의 구간합을 나눴다고 가정하자. 여기서 숫자가 하나 더 추가된다면 j+1개의 구간합으로 나눈 경우는 i-1까지의 j개의 구간합에 i+1을 추가한 경우, i-2개까지의 j개의 구간합에 i, i+1번째 수로 구간합을 하나 만드는 경우 ... 이렇게 하여 최댓값이 dp에 들어간다. 이걸 기반으로 문제를 풀어보자.

        int n = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());


        int[] prefix = new int[n+1];
        int[][] dp = new int[n+1][m+1];         //dp[i][j]: i번째 숫자까지 j개의 부분합으로 나눴을 때 최대 구간합

        for(int i = 0; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = -32768 * 101;
            }
        }

        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + Integer.parseInt(reader.readLine());
        }

        dp[1][1] = prefix[1];

우선 구간합을 이용하는 문제이므로 배열에서 prefix sum을 구하여 저장해준다. 그리고 dp를 초기화한다.

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

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

이후 위 규칙에 맞춰 계산을 한다. 만약 i번째 수를 포함하지 않는 경우 dp[i][j]=dp[i-1][j]이다. 또, j가 1이면 사용할 구간합 공식(prefix[i]-prefix[k+1])으로 구할 수 없으므로 따로 계산을 해준다. 이후 k에 대해 점화식을 적용하여 j-1개의 구간합에 새 구간합을 추가하여 가능한 경우 중 최댓값을 구하여 출력한다.