백준 2228 - 구간 나누기

icpc.me/2228

 

M개 구간을 인접하지 않게 모두 사용하여 구간들의 합을 최대화시키는 문제이다.

 

동적계획법으로 풀 수 있으며 3차원, 2차원으로 메모이제이션을 할 수 있다.

풀이 - 3차원 DP

3차원으로 풀기 위해 다음과 같이 테이블을 설계한다.

 

dp[i][j][k] := i번째 구간에서 j번째 숫자를 택하고 길이 k만큼 부분합을 구했을 때 최대값 

 

다중 for 문을 통해 다음 구간은 몇번째 숫자를 택할지, 길이는 얼마나 정할지에 대해 탐색하면서 최대값을 구하면 된다. 또한 각 수의 값은 -32768 이상 32767 이하이므로 dp 테이블을 초기화할 때 부분합으로 나올 수 있는 -32768 * 100 이상이나 32767 * 100 이하의 값은 피하면서 초기화를 해주어야 동적계획법 수행에 문제가 발생하지 않는다.

 

또한 탑다운 dp를 할때 구간 M개를 사용하지 않았는데 수열의 끝에 도착한 경우 적절한 음수를 리턴하여 구간 M개를 다 사용하지 않은 최대값이 나오는 경우를 걸러줘야 한다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
 
int seq[100];
int prefix[100];
int dp[100][100][100];
 
int memo(int turn, int idx, int range);
 
int main()
{
    fill(&dp[0][0][0], &dp[0][0][0] + 100 * 100 * 100, -1e9);
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
        cin >> seq[i];
    
    prefix[0] = seq[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = seq[i] + prefix[i - 1];
 
    int res = -1e9;
 
    for (int i = 0; i < n; ++i)
        for (int j = 0; j + i < n; ++j)
            res = max(res, memo(0, i, j));
 
    cout << res;
}
 
int memo(int turn, int idx, int range)
{
    if (turn == m)
        return 0;
    
    int &ret = dp[turn][idx][idx + range];
 
    if (ret != -1e9)
        return ret;
    
    ret = prefix[idx + range] - prefix[idx] + seq[idx];
 
    // 만약 재귀호출을 더이상 할 수 없다면 tmp값의 갱신이 이루어지지 않아// 잘못된 값이 나올 수 있으므로 별도의 종료조건을 정했다.
    if (turn == m - 1)
        return ret;
 
    int tmp = -1e9;
 
    for (int i = idx + range + 2; i < n; ++i)
        for (int j = 0; j + i < n; ++j)
            tmp = max(tmp, memo(turn + 1, i, j));    
 
    return ret += tmp;
}

풀이 - 2차원 DP

2차원인 경우 테이블은 다음과 같이 구성될 수 있다.

 

dp[i][j] := i번째 수까지 j개 구간을 택했을 때 최대값

 

메모이제이션에 대해 크게 두가지 경우로 나뉜다.

 

i번째 수를 택하지 않는 경우: 이 경우 i - 1번째와 값이 같아질 것이므로 점화식은

dp[i][j] = dp[i - 1][j] 가 된다.

 

i번째 수를 택할 경우: 각 구간은 인접할 수 없으므로 1번째부터 i - 2번째 사이에서(그 값은 k라 하자) j - 1개의 구간을 택한 값과 k번째에서 i번째까지의 구간합을 더한 값 중에서 최대값을 가져와야 한다. 이를 점화식으로 표현하면

dp[i][j] = dp[i - 2][j - 1] + prefixsum[i] - prefixsum[k - 1] 꼴로 나타낼 수 있다.

 

이제 점화식을 토대로 for 문을 통해 계산하면 된다.

 

단, 이 과정에서 i - 2가 0보다 작아지는 경우와 i번째에서 구간의 개수가 i / 2보다 많아지는 모순이 발생할 때 적절히 재귀를 끊어야 RTE와 TLE를 예방할 수 있다. (33번째 줄)

 

전체코드

#include <bits/stdc++.h>
  
using namespace std;
 
int n, m;
int seq[101];
int prefix[101];
int dp[101][52];
 
int memo(int idx, int cnt);
 
int main() 
{
    fill(&dp[0][0], &dp[0][0] + 101 * 52, -1e9);
    cin.tie(0); ios::sync_with_stdio(false);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
        cin >> seq[i];
 
    for (int j = 1; j <= n; ++j)
        prefix[j] = prefix[j - 1] + seq[j];
 
    cout << memo(n, m);
}
 
int memo(int idx, int cnt)
{
    if (!cnt)
        return 0;
    
    if (idx < 0 || cnt * 2 - 1 > idx)
        return -1e9;
    
    int &ret = dp[idx][cnt];
 
    if (ret != -1e9)
        return ret;
    
    ret = memo(idx - 1, cnt);
 
    for (int i = idx; i > 0; --i)
        ret = max(ret, memo(i - 2, cnt - 1) + prefix[idx] - prefix[i - 1]);
 
    return ret;
}

메모리 6000짜리가 3차원, 2000짜리가 2차원으로 구현한 결과이다.