ALLERGY와 비슷한 상황에서 재귀함수 구축법 질문드립니다.

  • Laplace
    Laplace

    ALLERGY 같은 유형의 문제를 보면 기본적으로 음식을 선택하는 조합을 찾게 되는데 아래와 같은 재귀함수를 자주 구축하고 있습니다. for문을 봐주세요~

    void allergy3(int cur, long long selected, int minFood)
    {
        if (best <= minFood) return;
    
        if (selected == (1 << n) - 1)
        {
            best = min(best, minFood);
            return;
        }
        for (int next = cur + 1; next < m; ++next)
            allergy3(next, selected | foodlist[next], minFood+1);
    }
    

    allergy3(-1, 0, 0)의 형태로 함수를 동작시켜서

    0, 1, 2, ...., m-1의 원소들을 선택하는 모든 조합을 탐색합니다.

    그런데 문제를 조금 달리 생각해보면 각각의 원소를 선택하거나 안하는 상황으로 나눌 수 있습니다. 즉 2^m개의 경우의 수를 가진 탐색으로도 바라볼 수 있다는 것이죠. 따라서 아래와 같은 코드도 가능합니다.

    void allergy4(int cur, long long selected, int minFood)
    {
        //cur 범위 벗어난 경우
        if (cur == m) return;
    
        if (best <= minFood) return;
    
        if (selected == (1 << n) - 1)
        {
            best = min(best, minFood);
            return;
        }
    
        //선택 안함
        allergy4(cur + 1, selected, minFood);
        //선택함
        allergy4(cur + 1, selected | foodlist[cur], minFood + 1);
    }
    

    결과적으로 allergy3의 경우에는 mC1 + mC2 + mC3 + ... + mCm 가지 경우를 도출하고
    allergy4의 경우에는 2^m가지 경우를 도출합니다. 따라서 탐색하는 조합의 수는 동일합니다. (mC0을 제외하고...)

    제가 궁금한 점은 이 두 함수가 똑같은 답을 도출하느냐는 것입니다.

    일단 약간의 차이점은 allergy3의 경우 적어도 한개 이상의 원소를 선택한다는 점이 있는 것 같습니다.

    정리하자면 조합의 경우엔 탐색 순서를 고정시켜서
    for(int next = cur+1; ...)라는 반복문을 이용하여 코드를 짜고 있습니다. 이 코딩 방식과 선택하는경우, 선택하지 않는 경우로 나누는 코딩방식의 논리적, 결과적 차이점이 있는지 매우 궁금합니다. ^^


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