ALLERGY 계속 오답만 뜨네요 도와주십시오.

  • innocentchris
    innocentchris

    개인적으로 몇번이나 테스트 케이스를 만들어서 돌려봐도 정답이나 제출만 하면 계속 오답이 나와서 여쭈어보게 되었습니다.

    꼭 부탁드립니다. 안되는 테스트케이스가 있으면 그것만이라도 보여주십시오.

    알고리즘은 대략적으로 먹는 아이들을 비트로 만든후
    각 음식을 최소로 중첩해서 모든 아이들을 먹일수 있게 하는 알고리즘입니다.

    예를들어 a b c d가 있다고 하면 비트는 1111(2)=15, 즉 15가 최종 목표입니다.

    음식이 1.(a b),2.(b c),3.(c d)라면
    1.(a,b)=0011 =3
    2.(b,c)=0110=6
    3.(c,d)=1100=12
    입니다.

    여기서 1번에 3번을 쌓으면 15가 되어 완성중 하나로 취급합니다.

    쌓는 과정은 이렇습니다.
    1번에 2번을 쌓을경우 0100이 새롭게 추가되어 0111이 됩니다.3번을 추가할경우 1000이 추가되어 1111이 되어 비트가 완성됩니다. 다만 이 과정에서 3번(1100)은 쌓여있는 0100(새로운 비트만) 을 완벽히 포함하고 있기에 3번을 쌓고 2번을 버립니다. 따라서 총 스택은 2번입니다.

    이런식으로 가장 최소로 쌓아 목표를 달성한 음식물을 제출합니다.

    코드를 첨부합니다..

    #include <iostream>
    #include <string>
    #include <map>
    #include <vector>
    #include <math.h>
    using namespace std;
    //typedef __int64 int64_t;
    static int64_t totalCt = 0;
    static int64_t goal = 0;
    
    
    struct food
    {
        int64_t num;
        int64_t currentSum;
        vector<int64_t> stack;
        //현재 음식의 중첩 횟수
        int ct;
    public:
        food()
        {
            ct = 0;
            num = 0;
            currentSum = 0;
        }
        //새로 음식값을 받아 쌓는다.
        void calculate(int64_t val)
        {
            //다 쌓여서 쌓을필요가 없다.
            if (currentSum == goal)
            {
                return;
            }
            //아직 한번도 쌓인 음식이 아닐경우,
            if (currentSum == 0)
            {
                //이 음식과 주어진 음식에 다른 비트가 존재할 경우,
                //예를들면 내음식이 0001이고 주어진 음식이 0011이라면 0010 만큼이 새로운 타켓이므로 "쌓는다"
                int64_t tem = (val - (val&num));
                if ((tem) > 0)
                {
                    //쌓여진 지금 음식의 최종값
                    currentSum = tem + num;
                    //쌓인 음식을 스택에 넣어준다.
                    stack.push_back(tem);
                    //쌓인 횟수.
                    ct++;
                }
                reCalculateCurrentSum();
    
            }
            else
            {
                bool add = false;
                //스택에 돌아가면서 쌓여진 음식중 지금 새로 들어온 음식으로 대체할수 있는지 찾는다.
                //예를들어 1010이 쌓여져 있다면 11010으로 대체할수 있다.
                for (int i = 0; i < stack.size(); i++)
                {
                    //새로운 음식이 기존 음식을 포함할경우,
                    if ((val&stack[i]) == stack[i])
                    {
                        //스택에서 버리고
                        stack[i] = -1;
                        //카운트를 깍는다.
                        ct--;
    
                        add = true;
                    }
                }
                reCalculateCurrentSum();
                //이미 대체했으므로 무조건 쌓아야 한다.
                if (add)
                {
                    int64_t tem = (val - (val&currentSum));
                    stack.push_back(tem);
                    ct++;
                    reCalculateCurrentSum();
                }
                //음식을 대체한 경우가 아니면, 이 음식이 새로운 비트를 가지고 있는지 확인
                else
                {
                    //여태 쌓여진거 말고 새로운 비트가 있을경우 쌓는다.
                    int64_t tem = (val - (val&currentSum));
                    if (tem > 0)
                    {
    
                        stack.push_back(tem);
                        ct++;
                        reCalculateCurrentSum();
                    }
                }
    
    
            }
            //음식이 다 쌓여서 쌓을 필요가 없다.
            if (currentSum == goal)
            {
                if (this->ct < totalCt)
                {
                    totalCt = ct;
                }
            }
        }
        void reCalculateCurrentSum()
        {
            currentSum = this->num;
            for (int i = 0; i < stack.size(); i++)
            {
                if (stack[i] == -1)
                {
                    continue;
                }
                int64_t tem = (stack[i]);
                currentSum += tem;
            }
        }
    };
    int main(int arg, char* args[])
    {
        string nums;
    
        getline(cin, nums);
        int num = stoi(nums);
        vector<int> answer;
        //몇번 진행할것인지.
        for (int ab = 0; ab < num; ab++)
        {
            //음식숫자
            int foodNum;
            //친구숫자
            int friendNum;
            //최종 목표가 될 숫자. 초기화
            goal = 0;
            //현재 최소 카운트. 일단 일정한 큰 수
            totalCt = 100000;
            cin >> friendNum;
            cin >> foodNum;
            std::map<string, int64_t> friendMap;
    
            for (int i = 0; i < friendNum; i++)
            {
                string name;
                cin >> name;
                //각 아이들을 받아올때마다 아이들에게 비트 자리수 하나식을 준다.
                friendMap[name] = pow(2, i);
                //최종 목표가 될 숫자에 아이들 마다 받은 비트를 더한다. 즉 4명이면 1111(2)가 된다.
                goal += friendMap[name];;
            }
            //음식 받아오기
            vector<food*> foods;
            for (int i = 0; i < foodNum; i++)
            {
                int fNum = 0;
                cin >> fNum;
    
                int64_t foodValue = 0;
                //음식을 먹을 애들.
                for (int j = 0; j < fNum; j++)
                {
                    string fname;
                    cin >> fname;
                    //먹을 애들 하나마다 이 음식에 값을 세팅한다. 예를들어 1번아이와 3번 아이가 먹는다면 이 음식값음 0101(2)이다.
                    foodValue += friendMap[fname];
                }
    
                //지금까지 존재한 음식에 방금 받은 음식을 "쌓는다" 이 과정에서 필요 없는 음식은 쌓이지 않고 버려진다.
                for (int tf = 0; tf < foods.size(); tf++)
                {
                    foods[tf]->calculate(foodValue);
                }
                //새로운 음식을 만들어 음식 어레이에 넣는다.
                food *f = new food();
                f->num = foodValue;
                f->ct = 1;
                f->reCalculateCurrentSum();
    
                foods.push_back(f);
            }
    
            int lessCt = 10000;
            for (int tf = 0; tf < foods.size(); tf++)
            {
    
                food *f = foods[tf];
    
                //int64_t sum = f->currentSum;
                ////음식들중 합이 목표치인 경우,
                //if (sum == goal)
                //{
                //  //최소의 쌓아진 합으로 도달한것을 찾아서
                //  if (lessCt > f->ct)
                //  {
                //      //최소에다가 넣는다.
                //      lessCt = f->ct;
                //  }
                //}
                delete f;
            }
            //정답을 가지고 있는다.
            answer.push_back(totalCt);
        }
        ///출력
        for (int i = 0; i < answer.size(); i++)
        {
            cout << answer[i] << endl;
        }
    }
    

    9년 전
3개의 댓글이 있습니다.
  • JongMan
    JongMan

    일종의 휴리스틱을 사용하시는 것 같은데, 이 문제는 모든 가능한 경우의 수를 다 탐색하는 방향으로 푸셔야 합니다. 아니면 항상 반례가 존재할 수밖에 없습니다.


    9년 전 link
  • innocentchris
    innocentchris

    조언 감사드립니다. 하지만 저는 모든 가능한 조합을 모두 탐색했다고 생각했습니다.
    예를들면 첫번재 음식의 경우 뒤로 들어오는 모든 음식과의 조합을 다 탐색하게 됩니다.

    혹시 어떠한 부분에서 제가 놓쳤는지 조금더 지적해주시면 도움이 많이 되겠습니다.


    9년 전 link
  • wafter
    wafter

    같은 문제를 푼 사람입니다. 본 문제풀이에 어려움을 겪으시는 것 같아서 (저도 실력이 많이 없지만) 도움을 드릴 수 있을까 하여 위의 소스를 대강 분석해 보았습니다. 코드를 완전히 분석한 것은 아니지만, 프로그램의 로직의 오류를 두가지 정도 발견한 것 같습니다.

    첫째는, 이미 CurrentSum이 goal을 이룬 것은 고려하지 않는 것입니다. goal을 이루었다 해도 새로 들어오는 음식이 많은 친구들을 커버할 경우 goal을 이루는데 필요한 음식의 개수는 더 적어질 수 있습니다.

    둘째는, 현재 음식 정보를 stack에 쌓인 값하고만 비교한다는 것입니다. stack 에 쌓인 값 뿐 아니라 num 값도 비교해야 합니다. 그런데, 간혹 num이 불필요한 경우도 있을 수 있는데, 현재의 로직은 num값을 기준으로 한 상대적 값(증가분)을 stack에 저장하므로 num이 불필요한 경우는 처리하기가 매우 곤란해집니다. 프로그램을 수정해야 할 것 같습니다.

    반례를 아주 간단한 걸로 들어 드리겠습니다.
    [1] 친구 5명, 음식 5개
    5 5
    a b c d e
    2 a b
    2 b c
    1 d
    1 e
    3 c d e
    정답은 2 이지만 위의 코드는 4를 출력합니다.
    [2] 친구 2명, 음식 2개
    a b
    1 a
    2 a b
    정답은 1 이지만 위의 코드는 2을 출력합니다.


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