백준 2228번: 구간 나누기 (Java)

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

2228번: 구간 나누기

 

 

 

 

 

 

 

 

---

 

풀이

다들 2차원 배열로 잘 풀던데, 저는 머리가 그렇게는 안 돌아가서 3차원 배열을 만들었습니다.

 

1~N번째 수열의 값을 각각 arr[i]에 담아둡니다.

3차원 int 배열 dp[i][j][k]: 1~i번째 수를 j개의 구간을 이용하여 합하였을 때 최대값(k==0: i번째 수 미포함, k==1: i번째 수 포함)

그러면,

dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]), dp[i][j][1] = max(dp[i-1][j-1][0], dp[i-1][j][1]) + arr[i]

이 성립합니다.

 

실수하기 좋은 점

1) dp 배열 내 모든 값은 50 * (-32768) 이하로 초기화해야합니다: 적당히 -1억정도로 잡았습니다.

2) 다만, 처음 인덱스에서 참고하는 값은 0이 되도록 초기화합니다: 이런 edge case는 본인 성향에 맞춰 처리해줍시다.

3) i = j == 5와 같은 경우는 invalid합니다: j를 가능한 범위 내에서만 for문을 돌리도록 합니다.

 

cf) 반례

기본적인 반례입니다.

3 1
-100
1
2
 
3 1
-100
2
1
 
3 1
1
-100
2
 
3 1
2
-100
1
 
3 1
1
2
-100
 
3 1
2
1
-100
 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws 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[][][] dp = new int[N+1][M+1][2];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                Arrays.fill(dp[i][j], -100_000_000);
            }
        }
        int[] arr = new int[N+1];
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        dp[0][0][1] = 0;
        dp[0][0][0] = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= Math.min(M, i/2); j++) {
                dp[i][j][0] = Math.max(dp[i-1][j][1], dp[i-1][j][0]);
            }
            for (int j = 1; j <= Math.min(M, (i+1)/2); j++) {
                dp[i][j][1] = Math.max(dp[i-1][j-1][0], dp[i-1][j][1]) + arr[i];
            }
        }
        System.out.println(Math.max(dp[N][M][0], dp[N][M][1]));
    }
}