백준: Gold4 - 1043, 1062

</br> 이제 골드 4를 풀어보자~~
</br>

1043: 거짓말

https://www.acmicpc.net/problem/1043

거짓말을 할 수 있는 공연 개수 세기

void func(int i){
    if( !truth[i] ) return;
    for(int j = 1; j <= n; j++){
        if( graph[i][j] && !truth[j] ){
            truth[j] = 1;
            func(j);
        }
    }
}

// in main()
    vector< vector<int> > v;
    while( m-- ){
        int a;
        cin >> a;
        vector<int> p;
        for(int i = 0; i < a; i++){
            int b;
            cin >> b;
            p.push_back(b);
        }
        for(int i = 0; i < a; i++){
            for(int j = i+1; j < a; j++){
                graph[p[i]][p[j]] = 1;
                graph[p[j]][p[i]] = 1;
            }
        }
        v.push_back(p);
    }
    for(int i = 1; i <= n; i++){
        func(i);
    }
    int cnt = 0;
    for(int i = 0; i < v.size(); i++){
        cnt++;
        for(int j = 0; j < v[i].size(); j++){
            if( truth[v[i][j]] ){
                cnt--;
                break;
            }
        }
    }
    cout << cnt << endl;

처음 문제를 보고 공연 순서에 의미가 있나? 했는데 없었다
사람들 사이의 관계망… 같은 문제

ex)
(1, 3, 5, 7), (5, 6, 7), (2, 4), (3, 8, 9)
-> (1, 3, 5, 6, 7, 8, 9), (2, 4)

같이 연결된 사람들(공연을 본 사람들)을 파악해서 진실을 아는 사람이 있다면 다 진실을 안다고 표시한다.
</br>

1062: 가르침

https://www.acmcpc.net/problem/1062

알파벳을 k개 알 때 읽을 수 있는 단어 수의 최대

void func(int bit){
    int cnt = 0;
    for(int i = 0; i < v.size(); i++){
        cnt++;
        if( (bit | v[i]) != bit ) cnt--;
    }
    ans = max(ans, cnt);
}

// in main()
    alphabets[0] = 1;
    alphabets['c'-'a'] = 1;
    alphabets['n'-'a'] = 1;
    alphabets['t'-'a'] = 1;
    alphabets['i'-'a'] = 1;

    k -= 5;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        set<char> st;
        for(int j = 4; j < s.size() - 4; j++){
            if( !alphabets[s[j]-'a'] ) st.insert(s[j]);
        }
        if( st.size() > k ) continue;
        int t = 0;
        for(char c : st){
            t |= 1 << (c - 'a');
        }
        v.push_back(t);
    }
    if( k == 0 ){
        cout << v.size();
        return 0;
    }
    for(int i = 1; i < (1 << 26); i++){
        if( getOnes(i) == k ) func(i);
    }
    cout << ans << endl;

이번엔 조합을 비트마스킹으로 해 봤다
a, c, n, t, i는 무조건 포함해야 하므로 표시하고, 배울 수 있는 수 k에서 5개를 빼준다.
각 단어들이 앞 ‘anta’와 ‘tica’를 빼고 가지고 있는 알파벳들을 비트마스크로 표현한다.
그리고 (bit | v[i]) != bit을 통해 만약 현재 비트가 단어를 표현할 수 없다면 카운트하지 않았다.
</br>

---

골드 4는 어렵구나
제목에 인덱싱은 이제 안 해야지
</br>