백준 2228

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

2228번: 구간 나누기

 

 

생각의 흐름.. 

1. 처음엔 DFS 방식으로 구간 시작위치를 조합해서 구하려 했었다. 근데 다 생각해보니 답이 다르길래 뭐지 했는데 각 구간 길이가 다를 수도 있었다. 그래서 뭔가 이방식으로 풀어나가기가 애매했다. 

2. 구글링을 했는데 DP를 사용하는걸 확인을 했다. 

3. 좀 다른 분들 코드를 보다가, DP[ i ][ j ] 를 배열의 첫 번째 원소에서 i 번째 원소까지 j개의 구간으로 나눴을 때 최대 합으로 잡았었다. 그래서 DP[i][j] 는 i 번째원소가 포함되냐 / 안 되느냐로 각각 계산한 후 최댓값으로 갱신해나가는 방식을 생각했었다. 

4. 근데 이 방법은 DP[ i-1 ][ j ]의 값이 i-1번째 원소가 포함 되는건지 안되는건지 알 수 없다. 문제 조건에 이웃한 구간끼리 겹치거나 인접하면 안된다고 나와있으므로... 

5. 그래서 그냥 3차원 배열로 선언해서 푸신 분의 방식을 참고하여 풀었다. 

 

import java.util.*;
import java.io.*;
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++) {
                DP[i][j][0] = DP[i][j][1] = Integer.MIN_VALUE;
            }
        }

        for (int i = 0; i <= n; i++) {
            DP[i][0][0] = DP[i][0][1] = 0;
        }

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

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min((i+1)/2, m) ; j++) {
                DP[i][j][0] = Math.max(DP[i-1][j][0], DP[i-1][j][1]);
                DP[i][j][1] = Math.max(DP[i-1][j-1][0] , DP[i-1][j][1]) + num[i];
            }
        }
        System.out.println(Math.max(DP[n][m][0], DP[n][m][1]));
    }

}