[백준 2228] 구간 나누기

문제 출처

1. 구상

• 문제 이해부터 좀 힘들었음
  → 문제 이해 참고 링크

• 누적 합을 저장하는 배열 & 해당 위치를 탐색했는지 기록하는 배열 만들기

• 구간의 최대 합을 저장하는 배열 만들기

• 현재 위치 값을 구간에 넣지 않는다면 전 실행에서의 구간 최대 합을 저장
  현재 위치 값을 구간에 넣는다면 전 실행의 구간 최대 합 값과 {(위치 - 2)에서 (구간 - 1)로 구간을 나누었을 때 최대 합 + 현재 구간 ~ 배열 크기까지의 누적 합 }을 비교하여 최대 값을 저장
  
  

2. 구현

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

public  class Main {	
	
    //구간 최대 합 저장하는 배열
	public static int[][] dp;	
    //누적 합을 저장하는 배열
	public static int[] sum;
    //탐색했는지 기록하는 배열
	public static boolean[][] check;	
    //dp 배열의 빈 위치를 채워주는 상수
	public static final int INVALID =  -32768 * 100;
	
	
	public static void main(String[] args) throws Exception {
		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt();
		int m = s.nextInt();
		
		//(배열의 크기 + 1) * (구간 수 + 1) 크기만큼 
		dp = new int[n+1][m+1];	
        //1 ~ 배열의 크기로 저장할 수 있게 (배열 크기 + 1)만큼
		sum = new int[n+1];
        //(배열의 크기 + 1) * (구간 수 + 1) 크기만큼 
		check = new boolean[n+1][m+1];
		
        //누적 합 값을 sum 배열에 저장
		for (int i = 1; i < n+1 ; i++)
			sum[i] = s.nextInt() + sum[i-1];
		
        //dp 배열 초기화
		for (int[] row : dp) Arrays.fill(row, INVALID);
		
		System.out.print(DP(n, m));
		
		
				
	}
	
	
	public static int DP(int idx, int sec) {
    //idx = 위치, sec = 구간 수
    
   		//구간의 개수가 0이면 0 반환
		if (sec == 0)
			return 0;
		
        //위치 값이 음수라면 INVALID값 반환
		if (idx < 0)
			return INVALID;
		
        //이미 탐색했다면 해당 값 반환
		if(check[idx][sec])
			return dp[idx][sec];
		
        //탐색을 한다면 탐색 기록 남기기
		check[idx][sec] = true;	
        
        //idx 값을 구간에 포함하지 않는다면 idx-1 최대 값을 저장
		dp[idx][sec] = DP(idx-1, sec);
		
		/*idx 값을 구간에 포함한다면 idx-1 최대 값과 
        idx-2 위치에서 sec-1만큼 구간을 나눈 최대 값과 
        i-1 ~ idx까지의 누적 합을 더한 것 중 최대인 값을 대입*/
		for (int i = idx; i > 0; i--) 
			dp[idx][sec] = Math.max(dp[idx][sec], DP(i-2, sec-1) + (sum[idx] - sum[i-1]));	
		
		
		
		return dp[idx][sec];
	}
	
	
} 

코드 및 알고리즘 참고 링크