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을 먼저 봐야하는지궁금합니다


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

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


    10년 전 link
  • 4dimensionn
    4dimensionn

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


    10년 전 link
  • JongMan
    JongMan

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


    10년 전 link
  • 4dimensionn
    4dimensionn

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


    10년 전 link
  • gomdolfather
    gomdolfather

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


    10년 전 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;

    }


    10년 전 link

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