PACKING 문제 질문입니다!

  • universalee
    universalee

    절박도를 최대로 만드는 물건의 개수와 목록을 찾아주는 find라는 함수를 작성했습니다.

    void find(vector<string>& nameArr, vector<string>& answer, int n, int w)
    {
        if (n>N) return;
        if (solution(n, w) == solution(n + 1, w)) find(nameArr, answer, n + 1, w);
        else
        {
            answer.push_back(nameArr[n - 1]);
            find(nameArr, answer, n + 1, w - weights[n]);
        }
    }
    

    이 함수는 정답처리가 됩니다.

    void find(vector<string>& nameArr, vector<string>& answer)
    {
        int i = 1, j = W;
        while (i<N)
        {
            if (cache[i][j] == cache[i + 1][j]) ++i;
            else
            {
                answer.push_back(nameArr[i - 1]);
                j -= weights[i];
                ++i;
            }
        }
    }
    

    제가 초기에 작성했던 함수는 이 코드인데요. 제가 생각하기에는 위 두 코드가 동작하는 방식이 동일하다고 생각되는데 이 코드는 오답처리가 됩니다. 혹시 왜 오답처리가 되는지 아시는 분 있으면 답변 주시면 감사하겠습니다. ㅠㅠ


    9달 전
1개의 댓글이 있습니다.
  • SteelFox
    SteelFox

    재귀에서는 n의 범위가 [1, N + 1)인데 반복문에서는 [1, N)이라서 그럴 듯요


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