백준 2228번 : 구간 나누기

  험멈멈... 왜 어렵지....? 어려울 것 같은 문제가 아니었는데 어렵다! 이럴 수가... 난 바보인가바...

---

  풀이

  dp를 잘 정의해보자.

 

dp[n][m] : 첫 번째부터 n번째까지의 수들 중에서 m개의 구간을 선택했을 때 구간 합의 최댓값

---

  n번째까지의 수 중에서 n번째 숫자가 구간에 포함되지 않았을 경우

  이 경우 n번째 숫자가 없는 것과 마찬가지다.

 

dp [n][m] = dp [n-1][m]

---

  n번째까지의 수 중에서 n번째 숫자가 구간에 포함되었을 경우

 

구간끼리는 인접해서는 안되므로 k-1번째를 비워둬야 한다.

 

  이 경우 n번째 숫자는 마지막 구간, 즉 m번째 구간에 포함되었을 것이다. m번째 구간이 k번째 수부터 n번째 수까지라고 가정해보자. m-1번째 구간은 m번째 구간과 인접할 수 없으므로 k-1번째 수는 사용할 수 없다. 따라서 k-2번째 수까지만 사용해서 m-1개의 구간을 만들어야 한다.

 

dp [n][m] = dp [k-2][m-1] + sum(k, n)

 

  하지만 m번째 구간이 어디서부터 시작하는지 정확히 알 수 없으므로 for문을 돌려서 최댓값을 구해야 한다.

 

#include <iostream>

using namespace std;

int n, m;
bool visit[102][52];
int dp[102][52];
int sum[102];

int areaSum(int num, int area)
{
    if(area == 0) return 0;
    if(num < 2*area-1) return -987654321;
    if(visit[num][area]) return dp[num][area];
    
    visit[num][area] = true;    
    dp[num][area] = areaSum(num-1, area);
        
    for(int i = num; i >= 1; i--)
    {
        dp[num][area] = max(dp[num][area], sum[num] - sum[i-1] + areaSum(i-2, area-1));
    }
    
    return dp[num][area];
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;

    int seq;
    for(int i = 1; i <= n; i++)
    {
        cin >> seq;
        sum[i] = sum[i-1] + seq;
    }
    
    cout << areaSum(n, m);
    
    return 0;
}