콘서트 문제 문의드립니다.

  • gloryof11
    gloryof11

    안녕하세요!
    콘서트 문제 오답 원인을 찾지 못하고 있서 답답한 마음에 문의를 드립니다;
    아래 코드에서 어떤 부분이 문제가 될 수 있는지 조언 부탁드립니다.
    감사합니다.

    CONCERT

    #include <stdio.h>
    
    int TC;
    int N, VS, VM;
    int vol[50];
    int map[51][1001];
    int answer;
    
    int main(void)
    {
        // init
        for(int j=0;j<=50;j++)
            for(int k=0;k<=1000;k++)
                map[j][k] = -1;
    
        scanf("%d",&TC);
        for(int i=0;i<TC;i++)
        {
            scanf("%d %d %d",&N, &VS, &VM);
    
            for(int j=0;j<N;j++) 
                scanf("%d", &vol[j]);
    
            map[0][VS] = VS;
    
            for(int j=0;j<N;j++)
            {
                for(int k=0;k<=VM;k++)
                {
                    if(map[j][k] != -1)
                    {
                        if(k-vol[j] >= 0)
                            map[j+1][k-vol[j]] = map[j][k];
                        if(k+vol[j] <= VM)
                        {
                            if(k+vol[j] < map[j][k])
                                map[j+1][vol[j]+k] = map[j][k];
                            else
                                map[j+1][vol[j]+k] = k+vol[j];
                        }
                    }
                }
            }
    
            answer = -1;
            for(int j=VM;j>=0;j--)
            {
                if(map[N][j] != -1 && map[N][j] == j) {
                    if(map[N-1][j-vol[N-1]] == map[N][j]) continue; // 추가한 조건문  
                    answer = j;
                    break;
                }
            }
    
            printf("%d\n",answer);
    
            // init
            for(int j=0;j<N;j++)
                vol[j] = 0;
            for(int j=0;j<=N;j++)
                for(int k=0;k<=VM;k++)
                    map[j][k] = -1;
    
        }   
    
        return 0;
    }
    


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

    초기화를 한 번만 하는것이 문제가 될 수도 있다는 생각을 해 봅니다... :)


    6년 전 link
  • gloryof11
    gloryof11

    결과를 출력하고 사용한 배열만 다시 초기화를 하고 있습니다; (참고로, 샘플 예제는 맞는데 답안 제출시 오답이 나오고 있습니다..)


    6년 전 link
  • astein
    astein

    아... 그렇네요... 아래쪽까지 다 읽어보질 않았네요... :$

    아래의 예제를 한번 테스트 해 보세요.
    1
    1 10 10
    1


    6년 전 link
  • gloryof11
    gloryof11

    힌트를 참고하여 조건문을 추가했는데 아직도 오답이 뜨고 있습니다..... 혹시 추가로 문제점 보이시면 도움 부탁드립니다..
    (감사합니다ㅠ.ㅠ)


    6년 전 link
  • astein
    astein

    위에 써 놓은 예제의 답은 9입니다...

    확인 부탁드려요 ㅎㅎ

    테이블을 보니 문제를 잘못 이해하신게 아닌가 라는 생각도 드네요 :)


    6년 전 link
  • gloryof11
    gloryof11

    astein 님 감사합니다! 덕분에 문제를 해결하였습니다!!

    (문제 이해도 잘못했었고, 구현한 조건식에도 문제가 있었습니다;;)


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