백준 3259번 PEOPLE - C++(cpp) 풀이

---

 

1. N명의 거짓말쟁이 여부를 결정하는 모든 경우, 2^N가지를 전부 체크한다.
2. 어떠한 경우가 해가 되려면, 해당 경우를 기준으로 했을 때 모든 사람들의 진술에 모순이 없어야 한다.

 

1. N명의 거짓말쟁이 여부를 결정하는 모든 경우, 2^N가지를 전부 체크한다.

 N명의 거짓말쟁이 여부를 결정하는 모든 경우는 총 2^N가지이다. 각 경우가 유효한지 체크하는 데 O(2N)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(2N*2^N)이다. N이 최대 20밖에 되지 않으므로 브루트포스로도 해결이 가능하다.

 

2. 어떠한 경우가 해가 되려면, 해당 경우를 기준으로 했을 때 모든 사람들의 진술에 모순이 없어야 한다.

 어떠한 경우가 유효한지 체크하려면, 해당 경우를 기준으로 모든 사람들의 진술에 모순이 존재하는지 검사하면 된다. i번 사람을 진실한 사람으로 결정한 경우라면, i번 사람이 진실하다고 말한 사람들은 실제로 다 진실해야 하고, i번 사람이 거짓말쟁이라고 말한 사람들은 실제로 다 거짓말쟁이여야 한다. 반대로 i번 사람을 거짓말쟁이로 결정한 경우라면, i번 사람이 진실하다고 말한 사람 중 실제로는 거짓말쟁이인 사람이 존재하거나, i번 사람이 거짓말쟁이라고 말한 사람 중 실제로는 진실한 사람이 존재해야 한다.

반응형

---

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 21;
int N;
vector<int> K_statements[MAX];
vector<int> L_statements[MAX];

bool validate(int mask) {
    for (int n=0; n<N; n++) {
        bool n_is_lier = (mask & (1 << n)) == 0;
        
        if (!n_is_lier) {
            for (int j=0; j<K_statements[n].size(); j++) {
                bool x_is_lier = (mask & (1 << K_statements[n][j])) == 0;
                if (x_is_lier) return false;
            }
            for (int j=0; j<L_statements[n].size(); j++) {
                bool x_is_lier = (mask & (1 << L_statements[n][j])) == 0;
                if (!x_is_lier) return false;
            }
        }
        else {
            int lie_cnt = 0;
            
            for (int j=0; j<K_statements[n].size(); j++) {
                bool x_is_lier = (mask & (1 << K_statements[n][j])) == 0;
                if (x_is_lier) lie_cnt++;
            }
            for (int j=0; j<L_statements[n].size(); j++) {
                bool x_is_lier = (mask & (1 << L_statements[n][j])) == 0;
                if (!x_is_lier) lie_cnt++;
            }
            
            if (lie_cnt == 0) return false;
        }
    }
    
    return true;
}

int bruteforce() {
    for (int i=0; i<(1<<N); i++) {
        if (validate(i)) return i;
    }
    
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    
    int K, L, x;
    
    for (int i=0; i<N; i++) {
        cin >> K;
        
        for (int j=0; j<K; j++) {
            cin >> x;
            K_statements[i].push_back(x-1);
        }
        
        cin >> L;
        
        for(int j=0; j<L; j++) {
            cin >> x;
            L_statements[i].push_back(x-1);
        }
    }
    
    int result = bruteforce();
    
    for (int i=0; i<N; i++) {
        if ((result & (1 << i)) != 0) cout << "true\n";
        else cout << "false\n";
    }

    return 0;
}