[백준 BOJ] 2228. 구간 나누기

난이도

Gold V

문제 풀이

"\(\small f(idx, \space count) :\equiv\) 현재까지 만든 그룹의 수가 count일때, idx번째 숫자부터 그룹을 만들어서 얻을 수 있는 합의 최대값" 이라고 정의하자.

각 그룹은 이웃하면 안되기 때문에 최소 한칸이상은 떨어트려 놓아야 하기에, 다음처럼 함수를 전개할 수 있다.

따라서, 재귀적으로 문제를 해결할 수 있게 되고 겹치는 부분문제들이 발생하기 때문에 그 부분을 메모이제이션해주면 된다. 메모이제이션 배열을 N x M 크기로 만들어
dp[idx][count]로 값을 미리 저장해두면 된다.

기저 사례는 \(\small count = M\)인 경우와 \(\small count < M \wedge idx \geq N\) 인 경우이다.

전자는 묶어야할 그룹을 모두 묶어낸 것이니 0을 리턴해주면 된다. 반면, 후자는 불가능한 경우이기에 불가능한 값을 리턴해줘야한다.

int solve(int idx, int cnt, vector<int>& seq, vector<vector<int>>& dp) {
    if(cnt == M) return 0; //base case
    if(cnt < M && idx >= N) return MIN; //base case 2

    int& ret = dp[idx][cnt];

    if(ret != MIN) return ret;

    ret = MIN - 1;
    int summation = 0;
    for(int i = idx; i < N; ++i) {
        summation += seq[i];
        for(int k = 2; k < N; ++k) {
            ret = max(ret, solve(i + k, cnt + 1, seq, dp) + summation);
        }
    }
    
    return ret;
}

코드에서 재밌는 점은, 캐싱되어있는 값을 리턴한 이후 ret = MIN - 1로 설정하는 부분이다. 이 라인을 작성해주지 않는다면 TLE를 받게 되는데, 그 이유는 ret = MIN일때 코드에서 값이 계산되지 않았다고 판단하기 때문이다. 불가능한 경우에 대해서도 캐싱을 해줘야하는데, 그게 안되면 계속 불필요한 연산이 발생하고 그게 지수꼴의 시간복잡도로 나타나 결국엔 시간초과가 발생하는것이다. 따라서, 나는 불가능하다는 의미로 MIN - 1을 할당해주는 방식을 택했다.

이렇게 값을 계산해주면, 답은 \(\small max_{i = 0}^{N - 1}(f(i, 0))\)이니, 이것을 찾아 출력해주면 AC.

코드 전문

2228 // 구간 나누기