QUANTIZE 문제 런타임 에러가 어디서 발생하는지 모르겠습니다.

  • sonyy789
    sonyy789

    시작하는 인덱스 idx와 depth를 dp로 사용했습니다.
    gap은 모든 쌍(i,j) i <= j 에 대하여 최소 오차값을 미리 저장시켜놨습니다.

    [코드 입니다.]

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int t, n, s, inf = 1e9;
    int A[101], dp[101][11], gap[101][101];
    int solve(int idx, int depth){
        if(depth == s) return gap[idx][n];
        int &ret = dp[idx][depth];
        if(ret != inf) return ret;
        ret = gap[idx][n];
        for(int i = idx; i < n; i++)
            ret = min(ret, gap[idx][i]+solve(i+1,depth+1));
        return ret;
    }
    int main(){
        int i, j, k;
        scanf("%d", &t);
        while(t--){
            scanf("%d%d", &n, &s);
            if(n == 1 || n <= s){
                printf("0\n");
                continue;
            }
            // init
            memset(&gap, 0, sizeof(gap));
            for(i = 1; i <= 100; i++)
                for(j = 0; j <= 10; j++) dp[i][j] = inf;
    
            for(i = 1; i <= n; i++)
                scanf("%d", &A[i]);
            sort(A+1, A+1+n);
    
            for(i = 1; i <= n; i++){
                int p_sum = 0;
                for(j = i; j <= n; j++){
                    p_sum += A[j];
                    int avg = (int)(0.5+(double)p_sum/(j-i+1));
                    for(k = i; k <= j; k++)
                        gap[i][j] += (avg-A[k])*(avg-A[k]);
                }
            }
            printf("%d\n", solve(1, 1));
        }
    }
    

    8달 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.