algospot :: ALLERGY 알러지가 심한 친구들

문제 : https://algospot.com/judge/problem/read/ALLERGY

알고리즘 문제 해결 전략 p.429

책을 참고하지 않고 코드를 작성함

[알고스팟 STEP.1]

비트마스크를 이용해서 지금까지 음식을 먹을 수 있는 사람들을 저장하고, 모든 사람들이 음식을 먹을 수 있을 때에 음식의 수의 최소값을 출력했다.

*void getInput()

입력을 받는 함수이다. 

이름은 names벡터에 따로 저장해두고

FOR(i, n){
    cin >> names[i];
}

food번째 음식에 대해 음식을 먹을 수 있는 이름들이 나오면, 그 이름을 갖고 있는 인덱스를 names에서 찾아서 그 값을 비트마스크로 환산하여 allergic[food]에 더했다. 

이렇게 하면 food번째 (음식을 먹을 수 있는 사람)번째 자리는 1, (음식을 먹을 수 없는 사람)번째 자리는 0 으로 2진수가 생성된다.

    FOR(food, m){
        cin >> people;
        long long int bit = 0;
        FOR(j, people){
            cin >> temp;
            FOR(k, n){
                if(!strcmp(temp.c_str(), names[k].c_str())) {  //**strcmp 사용법
                    bit += (1LL << k);
                    break;
                }
            }
        }
        allergic[food] = bit;
    }

모든 사람들이 음식을 먹을 수 있는 경우는 미리 full에 계산해두었다.

full = (1LL<<n)-1;//**비트연산자 int넘어갈때

*void solve(long long int a, int sum, int index)

입력받은 값 들에 대해 문제를 푸는 함수이다.

그냥 0번째 음식 부터 차례대로 넣고/ 안넣고를 반복하여, m개의 음식에 대해 2^m가지 경우의 수를 모두 실행해보았다. 

a==full일 때, 지금까지 만든 음식의 수 sum을 best와 비교해서 업데이트 했다.

void solve(long long int a, int sum, int index){
//    cout << bitset<50>(a) <<" "<<sum <<"index : "<< index << endl;
    if(a==full){
        best = min(best, sum);
//        cout << "best updated to ... " <<  best << endl;
    }
    if(index == m) return;
    // index물건 넣음
//    cout << index << " 넣음--" << endl;
    solve(a|allergic[index], sum+1, index+1);
    //index 안 넣음
//    cout << index << " 안넣음--" << endl;
    solve(a, sum, index+1);
}

[알고스팟 STEP.2]

solve의 첫 줄에, 이미 sum이 best보다 큰 경우 더 이상 시행하지 않는 코드를 추가해서 pruning을 했다.

이미 sum이 best보다 크다면 어차피 그 시행에서 sum은 best보다 작은 값이 나올 수 없으므로 더 이상 실행해보지 않아도 된다.

[최종코드]

// // Created by HANLEEKYEUNG on 2017. 10. 19.. // #include <vector> #include <algorithm> #include <iostream> #include <cstring> #define FOR(var, ed) for(int var = 0 ; var<ed; var++) using namespace std; int tc, n, m, people; string temp; vector<long long int> allergic; vector<string> names; int best; long long int full; void getInput(){ cin >> n >> m; names.clear(); names.resize(n); allergic.clear(); allergic.reserve(m); full = (1LL<<n)-1;//**비트연산자 int넘어갈때 // cout << bitset<50>(full) << endl; FOR(i, n){ cin >> names[i]; } //for each food FOR(food, m){ cin >> people; long long int bit = 0; FOR(j, people){ cin >> temp; FOR(k, n){ if(!strcmp(temp.c_str(), names[k].c_str())) { //**strcmp 사용법 bit += (1LL << k); break; } } } allergic[food] = bit; // cout << bitset<50>(allergic[food]) << endl; } // FOR(i, m) // cout << bitset<20>(allergic[i]) << endl; } void solve(long long int a, int sum, int index){ // cout << bitset<50>(a) <<" "<<sum <<"index : "<< index << endl; if(sum >= best) return; if(a==full){ best = min(best, sum); // cout << "best updated to ... " << best << endl; } if(index == m) return; // index물건 넣음 // cout << index << " 넣음--" << endl; solve(a|allergic[index], sum+1, index+1); //index 안 넣음 // cout << index << " 안넣음--" << endl; solve(a, sum, index+1); } int main(){ // freopen("input.txt","r",stdin); cin >> tc; while(tc--){ getInput(); best = 51; solve(0, 0, 0); cout << best << endl; } }

[내가 헤맸던 부분]

- 비트마스크가 int범위를 넘어가서 long long int를 도입해야 했다. 처음에 full을 만들 때 full을 long long int로 선언했음에도 불구하고 
full = (1<<n)-1;
이렇게 코드를 작성하면 full이 int범위로 생성되었다.