[백준 2228번} 구간 나누기 (C++)

문제링크 : https://www.acmicpc.net/problem/2228

2228번: 구간 나누기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M;
int arr[101], dp[101][51];

int func(int n, int m)
{
    if(m==M) return 0; //구간 선택 종료 
    if(n<=0) return -MAX; //에러 (범위 밖)
    if(dp[n][m]) return dp[n][m]; //값이 있으면 바로 반환

    int sum = 0;   
    dp[n][m] = func(n-1, m); //(~n-1 + n+1~) (현재 n이 구간에 포함되지 않는 경우)
    for(int i=n; i>0; i--)
    {
        sum += arr[i]; //누적합
        dp[n][m] = max(dp[n][m], func(i-2, m+1) + sum); //(~n-2 + n~) (현재 n이 구간에 포함되는 경우)와 위에서 구한 구간과 비교
    }
    return dp[n][m];
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;

    for(int i=1; i<=N; i++) cin >> arr[i];

    cout << func(N, 0);
    return 0;
}

 

먼저 dp[N][M]은 N이 현재 위치이고, M은 현재 구간이다

그리고 갱신할 케이스가 아래와 같이 2가지가 존재한다.

현재 N이 구간에 포함된 경우
(?~N-2 + N~?)

현재 N이 구간에 포함되지 않은 경우
(?~N-1 + N+1~?)

 

 

재귀를 통해서 위 케이스 2가지를 통해 dp를 갱신하게 된다.

해당 재귀에서 N이 감소하는 방식으로 값 탐색이 이루어지기 때문에 N이 범위 밖으로 나가면 예외처리를 해준다.

그리고 구간에 대해 시작은 0으로 1개씩 추가해나가며 주어진 M개에 도달하면 종료한다.

 

현재 N이 구간에 포함되지 않은 경우는 말 그대로 구간에 포함되지 않았기 때문에 재귀로 값을 넘길 때 m은 그대로이다.

현재 N이 구간에 포함되는 경우는 구간이 하나 감소했으므로 m을 1 증가시켜서 넘겨준다.

해당 문제에서 인접하지 않은 구간을 체크해야 하므로 현재 누적합을 더한 이후 나머지 구간은 N-2를 하여 현재 위치 기준 전전값의 위치를 넘기게 된다.