백준 11066번

2일을 헤맸습니다... 동적계획법으로 1부터 k(소설 장 수)까지의 최소 부분합을 구하는 문제입니다.

dp[i][j]는 i장부터 j장까지의 최소합을 메모제이션 합니다. 그런데 자꾸 오답이 떠서 다른분들의 코드를 살펴봤더니 페이지의 부분합을 dp에 더해주더라구요.

그런데 저는 최소합에 왜 부분합을 더하지??를 2일동안 이해해보려고 하다가... 자려고 누웠는데 혹시 dp에 저장되는 값이 부분합만 있는것은 아닐까? 라고 생각한 결과

코드를 이해하는데 성공했습니다... 

이지의 부분합을 더하기 전 dp[i][j]에는 i부터 j까지의 페이지의 결합을 위한 값만이 저장되므로 모든 페이지를 합치는 경우의 값이 안들어가게 되는것이었습니다.

2일이나 걸렸지만(사실 오늘을 합하면 3일) 알고리즘을 모두 이해할 수 있어서 뿌듯합니다.

Kruth's optimization라는 최적화 기법이 있다고 하는데 오늘은 늦어서 다음에 찾아서 공부하려 합니다.

#include <cstdio>
#include <algorithm>
 
int min(int a, int b) {
    return a > b ? b : a;
}
 
int main() {
    int t;
    scanf("%d", &t);
 
    while (t--) {
        int k;
        scanf("%d", &k);
 
        int* pagesSum = new int[k+1]();
        int** dp = new int*[k + 1]();
 
        for (int i = 1; i <= k; i++) {
            int value;
            scanf("%d", &value);
            pagesSum[i] = pagesSum[i - 1] + value;
            dp[i] = new int[k + 1]();
        }
 
        for (int i = 1; i < k; i++) {
            for (int j = 1; i + j <= k; j++) {
                dp[j][i + j] = 123456789;
 
                for (int k = j; k < i + j; k++)
                    dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j]);
 
                dp[j][i + j] += pagesSum[i + j] - pagesSum[j - 1];
            }
        }
 
        printf("%d\n", dp[1][k]);
    }
}