백준 5175번 문제없는 문제 - C++(cpp) 풀이

---

 

1. N개 문제 중에 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다.
2. 모든 경우를 크기 순, 사전 순으로 탐색하면서 M개의 알고리즘을 모두 커버 가능한지 탐색한다.

 

1. N개 문제 중에 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다.

 N개 문제 중에서 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다. N=20이므로 총 2^20가지의 경우가 있고 이는 시간 내에 모두 탐색할 수 있다.

 

2. 모든 경우를 크기 순, 사전 순으로 탐색하면서 M개의 알고리즘을 모두 커버 가능한지 탐색한다.

 이제 모든 경우를 크기 순, 사전 순으로 탐색하면서 최초로 M개의 알고리즘을 모두 커버하는 경우를 찾아내면 된다. 크기 순, 사전 순으로 정렬하기 위해 각 경우를 비트마스크로 나타내고 1의 개수가 적은 순으로, 1의 개수가 같다면 값이 더 작은 순으로 정렬하면 크기순, 사전 순으로 정렬할 수 있다.

 

반응형

---

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 21;

int T, M, N;
int tags[MAX], cases[1 << 21];
string s;

int count_one(int x) {
    int ret = 0;
    
    while (x > 0) {
        ret += (x % 2);
        x /= 2;
    }
    
    return ret;
}

bool cmp(const int a, const int b) {
    int cnta = count_one(a), cntb = count_one(b);
    if (cnta == cntb) return a < b;
    else return cnta < cntb;
}

bool check(int mask) {
    int res = 0;
    
    for (int i=0; i<N; i++) {
        if ((mask & (1 << i)) != 0) res |= tags[i];
    }
    
    return res == ((1 << M) - 1);
}

int bruteforce() {
    for (int i=0; i<(1 << N); i++) cases[i] = i;
    sort(cases, cases+(1 << N), cmp);
    
    for (int i=0; i<(1 << N); i++) {
        if (check(cases[i])) return cases[i];
    }
    
    return 0;
}

void init_testcase() {
    memset(tags, 0, sizeof(tags));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int t = 0;
    cin >> T;
    while (t++ < T) {
        init_testcase();
        
        cin >> M >> N; getline(cin, s);
        for (int i=0; i<N; i++) {
            getline(cin, s);
            
            int idx = 0, x = 0;
            while (idx < s.size()) {
                while (idx < s.size() && s[idx] != ' ') {
                    x *= 10;
                    x += s[idx] - '0';
                    idx++;
                }
                
                tags[i] |= (1 << --x);
                x = 0;
                idx++;
            }
        }
        
        int ans = bruteforce();
        
        cout << "Data Set " << t << ": ";
        for (int i=0; i<N; i++) {
            if ((ans & (1 << i)) != 0) cout << (char)('A'+i) << " ";
        }
        cout << "\n\n";
    }

    return 0;
}