말도 안되는 질문일 수는 있지만...

  • User Avatar
    canuyes

    말도 안되는 질문일 수 있지만 여쭈어 보고싶은게 있습니다.
    간혹 문제를 풀다가 주어진 예제 입력도 만족하고,
    스스로 몇몇 테스트케이스를 만들어 시험해보아도
    옳은 답을 내놓는데, 제출을 하는 경우에는 오답을 내놓습니다.

    그 틀린 답을 내놓는 테스트 케이스를 알아내야 하는데,
    여기 계신 분들은 그런 테스트케이스를 찾는 노하우(?) 같은 것이 있으신지요?

    추가로, 혹시 가능하다면
    문제 ID : PACKING에 대하여,
    제 코드

    ~~~ c++
    #include
    #include
    #include

    using namespace std;

    struct THING{char name[21];int vol;int need;};
    struct PAIR{int x;int y;bool is;};
    struct ANSWER{int sum;int num;char name[50][21];};

    int CACHE[101][1001];
    PAIR pairs[101][1001];
    THING things[100];
    ANSWER answer[50];
    vector ind;

    /*
    int mkCACHE(int n,int w){
    int i,&ret=CACHE[n][w];
    PAIR temp;
    if(ret==-1){
    if(n==0||w==0){ret=0;}
    else{
    ret=mkCACHE(n-1,w);temp.x=n-1;temp.y=w;temp.is=false;
    for(i=w-things[n-1].vol;i>=0;i--){
    if(ret<mkCACHE(n-1,i)+things[n-1].need){
    ret=mkCACHE(n-1,i)+things[n-1].need;
    temp.x=n-1;temp.y=i;temp.is=true;
    }}
    pairs[n][w]=temp;
    }}
    return ret;
    }
    */

    int mkCACHE(int N,int W){
    int i,j,k;
    PAIR temp;
    for(i=0;i<=N;i++){
    for(j=0;j<=W;j++){
    if(i==0||j==0){CACHE[i][j]=0;}
    else{
    CACHE[i][j]=CACHE[i-1][j];temp.x=i-1;temp.y=j;temp.is=false;
    for(k=0;k<=j-things[i-1].vol;k++){
    if(CACHE[i][j]<CACHE[i-1][k]+things[i-1].need){
    CACHE[i][j]=CACHE[i-1][k]+things[i-1].need;
    temp.x=i-1;temp.y=k;temp.is=true;
    }
    }
    pairs[i][j]=temp;
    }}}
    return CACHE[N][W];
    }

    void backtrack(PAIR temp){
    PAIR x=temp;
    while(x.x!=-1&&x.y!=-1){
    if(x.is==true){ind.push_back(x.x);}
    x=pairs[x.x][x.y];
    }
    return;
    }

    int main(void){
    int i,j,N,W,T;
    PAIR temp;
    cin>>T;
    for(i=0;i cin>>N>>W;
    for(j=0;j<=N;j++){memset(CACHE[j],-1,sizeof(int)*(W+1));}
    for(j=0;j<=N;j++){
    for(int k=0;k<=W;k++){
    pairs[j][k].x=-1;pairs[j][k].y=-1;pairs[j][k].is=0;
    }}
    ind.clear();
    for(j=0;j cin>>things[j].name;
    cin>>things[j].vol;
    cin>>things[j].need;
    }
    answer[i].sum=mkCACHE(N,W);
    backtrack(pairs[N][W]);
    answer[i].num=ind.size();
    for(j=0;j }
    for(i=0;i cout< for(j=answer[i].num-1;j>=0;j--){cout< }
    system("PAUSE");
    return 0;
    }
    ~~~

    가 어떤 인풋에서 틀린 아웃풋을 내는지 알고싶습니다.
    코드가 상당히 더러운(?)것을 잘 알고 있기에
    코드 분석보다는
    아무 인풋이나 틀린 인풋을 하나만 알기 원합니다..ㅠㅠ


    13년 전
5개의 댓글이 있습니다.
  • User Avatar
    dacchur

    반복적으로 같은 변수를 사용하는 경우가 많은데, 간혹 초기화를 생략하는 실수가 있더라고요. 물론 살펴 보셨겠지만요.^


    13년 전 link
  • User Avatar
    Kureyo

    DP랑 2n백트랙킹을 같이 구현해서 랜덤데이타를 계속 던져보세요-


    13년 전 link
  • User Avatar
    canuyes

    감사합니다!
    스캐폴딩을 말씀하시는 것 같은데, 사용해보니 정말 잘 해결 되었습니다.
    감사합니다!!


    13년 전 link
  • User Avatar
    Being

    느리지만 확실한 풀이를 구현해서 랜덤 데이터를 마구 던져보는 건 공부할 때 정말 큰 도움이 됩니다. :)


    13년 전 link
  • User Avatar
    canuyes

    답변 감사드립니다^


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