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

 

 

 

이런 문제를 처음 봤을 때 어떻게 접근해야 할까?

 

먼저 종이에 예제 입력을 그려보고 어떻게 풀 지 생각한다.

일단 다이나믹 프로그래밍을 사용해야 할 것 같으니, dp 배열을 어떻게 디자인 할 지 생각한다. ( ex. dp[i][j] = i번째 수 까지 사용하고, 구간 j개를 사용했을 때의 최대 구간합 / 초기값 설정 / 탑다운 or 바텀업 )

문제 상황에 맞춰서 dp배열을 디자인한다. 1차원으로 부족할 것 같으면 차원을 하나 더 늘려서 생각해본다.

종이에 dp배열을 그려놓고 어떤 방식으로 채워갈지 고민한다.

이전에 푼 문제에서 얻은 아이디어를 적용할 수 있는지 고민하면서, 점화식을 어떻게 세울 지 생각한다.

 

 

 

 

import java.io.*;
import java.util.*;

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

		for(int i=0; i<N+1; i++){
			for(int j=1; j<M+1; j++){
				dp[i][j] = -3276800;
			}
		}

		dp[1][1] = arr[1];

		for(int i=2; i<N+1; i++){
			for(int j=1; j<M+1; j++){

				dp[i][j] = dp[i - 1][j];

				int num = j == 1 ? -1 : 0;

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

					
				}												
				
			}
		}

		System.out.println(dp[N][M]);

	}
}