[BOJ] 백준 2228번 구간 나누기 (Java)

#2228 구간 나누기

난이도 : 골드 5

유형 : DP / 누적합

2228번: 구간 나누기

▸ 문제

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

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

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

 

▸ 입력

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

 

▸ 출력

첫째 줄에 답을 출력한다.

 

문제 풀이 

N개의 수로 이루어진 배열에서 M개 구간을 나눠 구간합의 최댓값을 구하는 문제이다. 

 

📚 조건

• N ( 1 <= N <= 100)
• M ( 1 <= M <=⌈(N/2)⌉
• 배열에 들어가는 수의 범위 ~32768 ~32767
• 구간이 겹쳐있거나 인접해있어서는 안된다.

 

하향식 풀이로 구간이 M개를 나누어지는 순간 최대의 합을 가지는 구간합을 구하면 된다.

누적합을 통해 구간 합 구하기

1. 주어진 구간 데이터를 누적 합으로 저장

dp배열로 다룰 변수로는 배열 인덱스 idx, 구간 수 section으로 지정하고 입력받은 배열 값들을 누적합 배열로 저장한다.

sum = new int[n+1];
for(int i=1; i<n+1; i++) {
	sum[i] = sum[i-1] + Integer.parseInt(br.readLine());	
}

 

2. dp배열 초기값 설정

배열에 들어가는 수의 범위가 -32768 ~32767이기때문에 처음으로, Init값을 -33333으로 잡아버린 나는 당연히 음수 누적합이 -33333이 넘을 수 있다는 사실을 간과해버리고 있었다. 그러면 누적합의 값이 더 작을 수 있으므로 초기화 값이 될 수 없다. 

 

그래서 최솟값 -32768과 n의 최대 크기 100을 곱하여 Init = -32768*100; 로 초기값을 설정해줬다.

 

3. 구간 합의 최댓값 구하기

완전탐색이 진짜 다른 조건들 하나도 생각안하고 그냥 top-down 재귀를 사용하면 되니깐 너무 편하다.

아 그런데, 누적합이라서 재귀 위에 for문으로 감싸주었던 부분은 살짝 고민이 필요한 부분이었다.

1. idx가 구간 section에 포함되지 않은 경우 idx-1의 최댓값과 동일하다.
   1. dp[idx][section] = solve(idx-1, section); 
2. idx가 구간 section에 포함되는 경우 이제 다음 구간을 for문을 돌려 탐색하면 된다.
   1. 구간은 겹쳐있거나 인접해있어서는 안된다. 그래서 다음 재귀함수는 한 칸 뛰어서 i-2부터 탐색해주면 된다. 
   2. dp[idx][section] = max (dp[idx][section], max(dp[i-2][section-1]) + sum(arr[i] ~ arr[n]));

dp[idx][section] = solve(idx-1, section);
for(int i = idx; i>0; i--) {
	dp[idx][section] = Math.max(dp[idx][section], solve(i-2, section-1)+(sum[idx]-sum[i-1]));
}

 

3-1. 방문 여부 체크

마지막으로, 음수로 뒤덮인 누적합 배열에서 방문을 했는지 안했는지 int값으로 판단하는 것은 거의 불가능했다.

if(dp[idx][section] ≠ Init) return dp[idx][section];  이런 조건들은 그냥 가볍게 무시되고 시간초과가 발생하였다.

 

그래서 결국 그래프 탐색할 때 처럼, boolean함수로 처리하였다.

if(checked[idx][section]) return dp[idx][section];

 

이와 같은 풀이로 예제를 돌리면 dp배열의 값은 다음과 같다.

배열 arr	-1	3	1	2	4	-1
누적합 sum	-1	2	3	5	9	8

 

구간 개수 \ 배열 idx	1	2	3	4	5	6
1	-1	3	4	6	Init	Init
2	Init	Init	0	5	9	9

 

풀이 코드 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int n,m;
	static int[] sum;
	static int[][] dp;
	static boolean[][] checked;
	static int Init = -32768*100;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		sum = new int[n+1];
		for(int i=1; i<n+1; i++) {
			sum[i] = sum[i-1] + Integer.parseInt(br.readLine());	
		}

		
		// - 32768 ~ 32767
		dp = new int[n+1][m+1];
		checked = new boolean[n+1][m+1];
		for(int i=0; i<n+1; i++) {
			Arrays.fill(dp[i], Init);			
		}
		
		System.out.println(solve(n,m));

	}
	
	static int solve(int idx, int section) {
		if(section == 0 ) return 0;		
		if(idx < 0 ) return Init;
		
		if(checked[idx][section]) return dp[idx][section];
		
		checked[idx][section] = true;
		dp[idx][section] = solve(idx-1, section);
		for(int i = idx; i>0; i--) {
			dp[idx][section] = Math.max(dp[idx][section], solve(i-2, section-1)+(sum[idx]-sum[i-1]));
		}
		
		return dp[idx][section];
		
	}
}