11066 파일합치기

#include <stdio.h>
 
int main() {
    int t;
    scanf("%d", &t);
 
    while (t--) {
        int n;
        scanf("%d", &n);
 
        int dp[501][501] = { 0 };
        int sum[501] = { 0 };
        for (int i = 1; i <= n; i++) {
            int val;
            scanf("%d", &val);
 
            sum[i] = sum[i - 1] + val;
        }
 
        for (int len = 1; len < n; len++) {
            for (int st = 1; st + len <= n; st++) {
                int end = st + len;
 
                int minV = 10000000000;
                for (int mid = st; mid + 1 <= end; mid++) {
                    int tmp = dp[st][mid] + dp[mid + 1][end];
 
                    if (minV > tmp)
                        minV = tmp;
                }
 
                dp[st][end] = minV + (sum[end] - sum[st-1]);
            }
        }
        printf("%d\n", dp[1][n]);
    }
}

매커니즘 자체는 전혀 이해가 안 된다.

왜 이런 점화식이 나오는건지..

웃긴건, 다른 사람 풀이를 보면서 점화식을 익혔는데도

구현 하는데에도 시간을 꽤 썼다는거...ㅋㅋ

한심하다