Quantization 기저사례 조건에 대해 질문 있습니다.

  • 4dimensionn
    4dimensionn
    #include <cstdio>
    #include <vector>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int INF = 987654321;
    int n, s;
    int data[102];
    int cache[102][12];
    int errCache[102][102];
    int minError(int idx, int size){
        int sum=0;
        int& errSum=errCache[idx][size];
        if(errSum!=-1)return errSum;
        errSum=0;
        for(int i=idx;i<idx+size;++i)sum+=data[i];
        int avg = (int)(0.5 + (double)sum/size);
        for(int i=idx;i<idx+size;++i)errSum+=(data[i]-avg)*(data[i]-avg);
        //printf("%d %d : %d %d\n",idx,size,avg,errSum);
        return errSum;
    }
    int process(int idx, int group){
        if(idx==n) return 0;
        if(group==0)return INF;
        if(group==1)return minError(idx,n-idx+1);
        int& ret = cache[idx][group];
        if(ret!=-1)return ret;
        ret = INF;
        for(int i=1;i+idx<=n;++i){
            ret = min(ret,minError(idx,i)+process(idx+i,group-1));
        }
        return ret;
    }
    int main(){
        int t;
        for(scanf("%d",&t);t;--t){
            memset(cache,-1,sizeof(cache));
            memset(errCache,-1,sizeof(errCache));
            memset(data,0,sizeof(data));
            scanf("%d%d",&n,&s);
            for(int i=1;i<=n;++i){
                scanf("%d",&data[i]);
            }
            sort(data+1,data+1+n);
            printf("%d\n",process(1,s));
        }
    
    }
    

    제가 궁금한 부분은 process함수에서 기저사례를 처리할때
    왜 idx==n 이부분을 먼저 처리 해야하는가 입니다.
    idx가 n에 도달했다고 하더라도 group이 0이라면 묶을 수 있는 방법이 없으므로 INF를 반환해야 된다고 생각해서 처음에 idx==n을 처리하는부분이 없이 코드를 작성하고 제출하였더니 오답이 나왔습니다.
    이 코드는 정답을 받은 코드인데 왜 저 부분에서 group예외를 처리하기전에 idx==n을 먼저 봐야하는지궁금합니다


    9년 전
6개의 댓글이 있습니다.
  • JongMan
    JongMan

    group이 2개 이상 남은 상태에서 idx==n에 도달한 상태를 고려해 보시면 알 수 있을 것 같네요.


    9년 전 link
  • 4dimensionn
    4dimensionn

    그럼 이런식으로 하면 안되나요?
    if(group==0)return INF;
    if(group==1)return minError(idx,n-idx+1);
    if(idx==n) return 0;


    9년 전 link
  • JongMan
    JongMan

    해 보진 않았지만 아마 되지 않을까요?;; 근데 사실 관계에 있어서, idx==n 이면 남은 그룹이 몇 개건 무조건 0이 답이어야 맞는 것이죠. 반대로 남은 그룹이 0개인 경우에는 idx < n인가 아닌가를 따져야 하므로, idx == n을 먼저 확인하는 것이 이해하기 쉽겠죠?


    9년 전 link
  • 4dimensionn
    4dimensionn

    n에 도달했을때 group이 0이여도 0을 반환해야 한다는게 이해가 잘 가지않습니다. ㅜㅜ


    9년 전 link
  • gomdolfather
    gomdolfather

    group 이 1인 기저사례를 이미 처리하셨기 때문에
    group이 0인 기저사례는 나오지 않습니다.
    idx가 n인 경우는 group이 최소 1이상인 경우만 나오게 됩니다.


    9년 전 link
  • gomdolfather
    gomdolfather

    group이 0인 기저사례를 처리하도록 고친 코드입니다.

    int process(int idx, int group){
    if(idx==n+1) return 0;
    if(group==0)return INF;

    int& ret = cache[idx][group];
    if(ret!=-1)return ret;
    ret = INF;
    for(int i=1;i+idx<=n+1;++i){
        ret = min(ret,minError(idx,i)+process(idx+i,group-1));
    }
    return ret;

    }


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