3018 캠프파이어

 

노래 개수를 저장하는 배열을 따로 만들어서 1이 들어오면 알고있는 곡의 개수를 하나 증가시키고 

 

1이 없으면 알고있는 곡의 개수가 가장 많은 걸 찾아서 전부 그 곡의 개수로 맞춰주게 구현했는데 틀렸다..

 

알고보니 이 문제는 곡의 개수로 구하면 안 되고 곡의 종류로 구분해야 했다!

 

1 2 4를 아는 사람이랑 1 2 5를 아는 사람이 곡을 공유하면 1 2 4 5를 알아야 하는데 개수로 구현을 하면 3곡을 알게 된다...!!!

 

 

이런 류의 문제는 비트마스크를 사용하면 편하게 구할 수 있다. 신기해

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int     main()
{
    int n;
    scanf("%d", &n);

    int e;
    scanf("%d", &e);

    vector<i64> ans(105);
    i64 num_one = 1;
    i64 comp = 1;
    for (int i = 0; i < e; i++)
    {
        int k;
        scanf("%d", &k);

        bool is_one = false;
        vector<int> v(k);
        for (int j = 0; j < k; j++)
        {
            scanf("%d", &v[j]);
            if (v[j] == 1)
                is_one = true;
        }

        if (is_one)
        {
            for (int j = 0; j < k; j++)
                ans[v[j]] |= num_one;
            num_one << 1;
            comp |= comp << 1;
        }
        else
        {
            i64 tmp = 0;
            for (int j = 0; j < k; j++)
                tmp = ans[v[j]] | tmp;

            for (int j = 0; j < k; j++)
                ans[v[j]] = tmp;
        }
    }

    for (int i = 1; i < 101; i++)
    {
        if (ans[i] & comp)
            printf("%d\n", i);
    }
    
    return 0;
}

 

---

 

으음 

 

1 2 3 4가 다 나와버렸네..

 

 

 

그래서 디버깅한다고 이렇게 출력해봤는데

 

comp랑 ans[i]가 다르더라도 comp & ans[i]가 1이 나온다.. 왜지... 

 

아 내 생각엔 comp & ans[i] 결과가 1이 돼서 그런 것 같다. 그냥 숫자가 나온듯

 

 

이렇게 바꿔주면 내가 생각한대로 돌아간다. 

 

이제 ans[i]가 1이 되는게 문제니 이 부분을 확인하면 될 것 같다. 

 

---

어헝헝헝 비트 싫어

 

num_one = num_one << 1; 여기서 문제였다. 기존 코드는 num_one을 shift하고 그걸 저장 안 해줘서 계속 1이었음.

 

그리고 comp도 마지막 1 없애줘야해서 또 문제였고....

 

고치니깐 맞았다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int     main()
{
    int n;
    scanf("%d", &n);

    int e;
    scanf("%d", &e);

    vector<i64> ans(105);
    i64 num_one = 1;
    i64 comp = 1;
    for (int i = 0; i < e; i++)
    {
        int k;
        scanf("%d", &k);

        bool is_one = false;
        vector<int> v(k);
        for (int j = 0; j < k; j++)
        {
            scanf("%d", &v[j]);
            if (v[j] == 1)
                is_one = true;
        }

        if (is_one)
        {
            for (int j = 0; j < k; j++)
                ans[v[j]] |= num_one;
            num_one = num_one << 1;
            comp |= comp << 1;
        }
        else
        {
            i64 tmp = 0;
            for (int j = 0; j < k; j++)
                tmp |= ans[v[j]];

            for (int j = 0; j < k; j++)
                ans[v[j]] = tmp;
        }
    }

    comp = ~(num_one)&comp;

    for (int i = 1; i < 101; i++)
    {
        if ((ans[i] & comp) == comp)
            printf("%d\n", i);
    }

    return 0;
}