[백준 2228] 구간 나누기 (JAVA)

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

2228번: 구간 나누기

 

DP와 누적합 문제로 풀어보면 좋을 문제인 듯 하다!!

점화식을 생각해내기 어려운 부분이 있어서 꼭 풀어보시면 좋겠다!

필자도 조만간 한번 더 풀어볼 예정이다 ,, ㅎㅎ

 

풀이

1.누적합을 이용하여 sum 배열에 넣어주고

 

2.dp 배열을 생성하여 

숫자의 최솟값은 -32768이고 N은 100개까지 이루어지므로, 

dp[0][1~m]까지를 -3276800으로 초기화한다.

 

3. dp[i][1~m] 는 i번 숫자를 1~m번 구간일때를 뜻한다.

i번 숫자를 포함할 때, 포함하지 않을 때를 나누어서 계산해준다.

숫자를 포함하지 않을 때는 dp[i-1][j]

숫자를 포함할 때는 구간이 어디서부터 시작됐는지도 고려해야 하기 때문에 포문을 사용하여 1~i번째까지를 확인한다.

k=1~i

dp[k-2][j]+sum[i]-sum[k-1];

만약, j와 k가 1이면 1개만 선택한 것으로 sum[i] 이다.

 

 

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, 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; i++) {
			int x=Integer.parseInt(br.readLine());
			sum[i] = x + sum[i - 1];
		}

		int[][] dp = new int[n + 1][m + 1]; // n번째 번호, m번째
		for (int j = 1; j <= m; j++) {
			dp[0][j] = -3276800;
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				dp[i][j] = dp[i - 1][j];
				for (int k = 1; k <= i; k++) {
					if (k >= 2)
						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]);
	}

}