[C++][백준 14610] 좋은 대회

문제

접근 방법

좋은 대회에 대한 기준은 문제에서 정의되어 있습니다.

1. 모든 참가자가 한 문제 이상을 풀어야 한다.
2. 모든 문제는 한 명 이상의 참가자에게 풀려야 한다.
3. 모든 문제를 푼 참가자는 없어야 한다.

참가자가 문제를 다 풀었는지, 하나도 풀지 못했는지를 알 수 있는 건 참가자의 맞춘 문제 수를 입력받았을 때 알 수 있습니다.

모든 문제를 한 명 이상의 참가자에게 풀렸는지는 가능성을 확인해 보아야 합니다.
밑으로 갈수록 깨진 부분에 의해 가려진 부분이 적다는 점을 활용하면 모든 문제가 한 명 이상에게 풀릴 수 있는지 확인할 수 있습니다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> map;
vector<int> K;
vector<bool> isSolved;
int N, M;
bool checkAll;

void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;

    map = vector<vector<int>>(N, vector<int>(M));
    K = vector<int>(N);
    isSolved = vector<bool>(M);

    for (int i = 0; i < N; ++i)
    {
        cin >> K[i];

        if (K[i] == 0 || K[i] == M)
        {
            checkAll = true;
        }

        for (int j = 0; j < M; ++j)
        {
            cin >> map[i][j];

            if (map[i][j] == 1)
            {
                isSolved[j] = true;
                --K[i];
            }
        }
    }
}

bool solve()
{
    if (checkAll)
    {
        return false;
    }

    for (int i = N - 1; i >= 0; --i)
    {
        for (int j = M - 1; j >= 0; --j)
        {
            if (map[i][j] != -1 || K[i] == 0)
            {
                break;
            }

            if (isSolved[j])
            {
                continue;
            }

            --K[i];
            map[i][j] = 1;
            isSolved[j] = true;
        }
    }

    for (int i = 0; i < M; ++i)
    {
        if (!isSolved[i])
        {
            return false;
        }
    }

    return true;
}

int main()
{
    input();
    cout << (solve() ? "YES" : "NO");
    return 0;
}

풀이

만약 참가자의 맞춘 문제 수를 입력받았을 때 0이거나 문제의 수만큼 받았다면 1번과 3번 규칙에 위반됩니다.

모든 문제가 풀리게 할 가장 좋은 방법은 이미 풀린 문제는 무시하고 풀릴 수 있는 문제 중 현재 참가자만이 풀 수 있는 문제를 푸는 것입니다.
맨 밑 우측부터 가려졌고 아직 풀 수 있는 문제가 남았다면 풀었다고 판단하였습니다.
밑으로 갈수록 좁아진다는 점에서 맨 밑 우측이 아닌 맨 위 좌측부터 시작하여도 문제는 없을 것입니다. (어차피 맨 위에 플레이어만 풀 수 있는 문제일 수도 있기 때문입니다)