[C++][백준 18248] 제야의 종

문제

접근 방법

문제가 이해하기 어렵게 되어있다.
쉽게 말해서 ABC에서 타종을 들었다면 ABC보다 적게 들은 사람은 ABC 이외에서 타종을 들으면 안 되고 ABC보다 많게 들은 사람은 ABC를 무조건 포함해야 하는 것이다.

그래야 특정 거리 R 이내에 모든 사람이 듣는다는 조건이 성립한다.

코드

#include <iostream>
#include <set>
using namespace std;
set<int> s;
int N, M;
bool isSub(set<int> &a)
{
    if (s.size() < a.size())
    {
        swap(s, a);
    }

    for (const int &i : a)
    {
        if (s.find(i) == s.end())
        {
            return false;
        }
    }

    return true;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int i = 0, k; i < N; ++i)
    {
        set<int> a;
        for (int j = 0; j < M; ++j)
        {
            cin >> k;

            if (k)
            {
                a.insert(j);
            }
        }

        if (!isSub(a))
        {
            cout << "NO";
            return 0;
        }
    }

    cout << "YES";
    return 0;
}

풀이

큰 집합에 작은 집합이 속하는지 확인해 주면서 큰 집합을 갱신해 주었다. 만약 도중에 작은 집합이 큰 집합에 속하지 않은 경우가 나타나면 실제로 불가능한 경우이므로 NO를 출력하면 된다.