ALLERGY 오답의 원인을 모르겠습니다.

  • 김영태
    김영태

    ALLERGY 오답의 원인을 모르겠습니다.

    문제 : ALLERGY

    작성한 알고리즘 핵심 내용

    • 조합 생성
    • 조합에 대응하여 음식을 합한 결과가 친구수와 동일한지 확인

    작성한 소스 내용

    • 기초 데이터를 입력 : Quiz::GetData()

      • m_index_cooks.insert(pair>(i, cooks)); 이곳에 음식 index (0 ~ N-1)와 음식을 먹을수 있는 친구 정보를 사전 입력해 놓음
    • void Quiz::Run() 함수에서 조합의 경우 수를 1 ~ 음식수 까지 생성하며 Combi함수를 호출

    • 조합 경우의 수를 만들면서 총 음식 개수와 동일할 때까지 모든 경우의 수를 확인

      • Combi(int* _pfull, int* _parr, int _candisize, int _arrsize, int _select_count) : 조합을 만듬
      • Combi 함수 안의 CalcCombi(int* _parr, int _select_dishs) : 함수에서 그때 그때 생성되는 조합마다 조건에 만족하는지 확인
    • 만족하면 return true --> 종료

    참고 의견

    • 소스 대부분이 구조 잡아서 구분한 것이라 좀 길어 보일지 모르겠는데요.대부분 구조 잡는 코드입니다.

    코드 블럭

    #include <iostream>
    
    #include<stdio.h>
    
    #include <map>
    #include <set>
    #include <vector>
    
    using namespace std;
    
    class Quiz
    {
    public:
        int m_result;
        int m_friend_total = 0;
        int m_dish_total = 0;
        set<string> m_friends;
        map<int, set<string>> m_index_cooks;
    
    public:
        void GetData();
        void Run();
        void GetResult(string& result);
    
    
        bool CalcCombi(int* _parr, int _select_count);
        bool Combi(int* _pfull, int* _parr, int _candisize, int _arrsize, int _select_count);
    
    };
    
    void Quiz::GetData()
    {
        m_result = 0;
        m_friend_total = 0;
        m_dish_total = 0;
        m_index_cooks.empty();      //  0번째 음식 - 친구 목록
    
        cin >> m_friend_total;
        cin >> m_dish_total;
    
    //  printf("friends %d\n", m_friends);
    //  printf("dishs %d\n", m_dishs);
    
        for (int i = 0; i < m_friend_total; i++)
        {
            char temp[11];
            cin >> temp;
            m_friends.insert(string(temp));
        }
        for (int i = 0; i < m_dish_total; i++)
        {
            int num = 0;
            cin >> num;
            set<string> cooks;
            for (int j = 0; j < num; j++)
            {
                char temp[11];
                cin >> temp;
                if (m_friends.find(string(temp)) != m_friends.end())
                {
                    cooks.insert(string(temp));
                }
            }
            m_index_cooks.insert(pair<int, set<string>>(i, cooks));
        }
    
    /*  for (map<int, set<string>>::iterator itr = index_cooks.begin(); itr != index_cooks.end(); itr++)
        {
            cout << itr->first << endl;
            for (set<string>::iterator it = itr->second.begin(); it != itr->second.end(); it++)
            {
                cout << it->c_str() << endl;
            }
        }*/
    }
    
    
    bool Quiz::CalcCombi(int* _parr, int _select_dishs)
    {
    //  for (int i = 0; i<_select_dishs; i++)
    //      printf("%5d", _parr[i]);
    //  printf("\n");
    
        set<string> temp;
        for (int i = 0; i < _select_dishs; i++)
        {
            for (set<string>::iterator it_s = m_index_cooks[_parr[i]].begin(); it_s != m_index_cooks[_parr[i]].end(); it_s++)
                temp.insert(*it_s);
        }
        if (temp.size() == m_friend_total)
        {
            m_result = _select_dishs;
            return true;
        }
    
        return false;
    }
    
    //  _setsize = 후보들 중 입력되는 값의 위치
    //  _arrsize = 입력해야할 공간 개수
    bool Quiz::Combi(int* _pfull, int* _parr, int _candisize, int _arrsize, int _select_count)
    {
        if (_arrsize == 0)
        {
            return CalcCombi(_parr, _select_count);
        }
        if (_candisize < _arrsize)
            return false;
        else
        {
            _parr[_arrsize - 1] = _pfull[_candisize - 1];
            if (Combi(_pfull, _parr, _candisize - 1, _arrsize - 1, _select_count) == true)
                return true;
            if (Combi(_pfull, _parr, _candisize - 1, _arrsize, _select_count) == true)
                return true;
        }
    }
    
    void Quiz::Run()
    {
        //  0 ~ N-1 까지 숫자중 조합을 구하는 방식,     1개 부터 N개까지
        for (int select_count = 1; select_count <= m_dish_total; select_count++)
        {
            int* pfull = (int*)malloc(sizeof(int) * m_dish_total);
            int* parr = (int*)malloc(sizeof(int) * select_count);
    
            for (int i = 0; i < m_dish_total; i++)
                pfull[i] = i;
    
            //               빈공간, 후보 size,  빈공간 size
            if (Combi(pfull, parr, m_dish_total, select_count, select_count) == true)
            {
                free(pfull);
                free(parr);
                return;
            }
            free(pfull);
            free(parr);
        }
    
        return;
    }
    
    void Quiz::GetResult(string& _rt)
    {
        char r[100];
        sprintf(r, "%d", m_result);
        _rt = r;
    }
    
    int main()
    {
    //  freopen("sample_input.txt", "r", stdin);
    
        int T;
        cin >> T;
    
        for (int test_case = 0; test_case < T; test_case++)
        {
            Quiz* quiz = new Quiz();
            quiz->GetData();
            quiz->Run();
            string result;
            quiz->GetResult(result);
    
            cout << result.c_str() << endl;
            //cout << "#" << test_case << " " << result.c_str() << endl;
    
            delete quiz;
        }
    
        return 0;
    }
    

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

    문제를 해석한 방법과 그 풀이 과정을 알려주셔야 도움을 드릴 수 있어요
    그게 아니라면 코드를 읽을 수가 있어야하는데 변수명때문에 무슨 내용을 쓴건지 모르겠어요 해석을 하려니 주석도 명확하지가 않아서 무슨 의미를 담고 있는지 알기 힘들어요


    6년 전 link
  • dyong
    dyong

    "친구들 모두가 음식을 먹으려면 최소 몇 가지의 음식이 있어야 하는가"가의 문제이고 0개부터 n개까지 음식을 만들었을 때 친구들이 모두 음식을 먹을 수 있는지 테스트해서 최적 결과를 도출해내는 방법으로 푼 것으로 보이긴해요


    6년 전 link
  • dyong
    dyong

    Combi와 CalcCombi에 대한 코드 내용을 좀 더 상세히 주석을 달아주시거나 설명해주시면 어디가 문제인지 알려드릴 수 있을 것 같아요


    6년 전 link
  • 김영태
    김영태

    bool Quiz::Combi(int* _pfull, int* _parr, int _candisize, int _arrsize, int _select_count)
    이함수가 핵심인데요. 여기에는 그림파일을 올리는 기능은 없나 보네요.ㅠㅠ (어디 공유할 곳도 없는데요)

    혹시 이메일 주소 열려주시면 Combi 함수 정리한 PPT가 있으니 보내드리겠습니다.

    -감사합니다.-


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