[C++][백준 34146] 잃어버린 섬

문제

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

접근 방법

대칭이 되기 위해선 중심을 기준으로 똑같은 수가 양옆에 나와야 합니다.
홀수의 경우에는 중심이 포함되는 점을 유의해야 됩니다.

코드

#include <iostream>
#include <cstring>
using namespace std;

int N, M;

int cnts[10001];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            int num;
            cin >> num;

            ++cnts[num];
        }
    }

    int oddCount = 0;

    for (const int &cnt : cnts)
    {
        if (cnt % 2)
        {
            ++oddCount;
        }
    }

    if (M == 1)
    {
        cout << "YES";
    }
    else
    {
        if (oddCount > N || (oddCount % 2 && N % 2 != 1) || (M % 2 == 0 & oddCount > 0))
        {
            cout << "NO";
        }
        else
        {
            cout << "YES";
        }
    }
    return 0;
}

풀이

나온 번호의 개수가 홀수인 것이 몇 개인지 세어줍니다.
홀수의 개수가 N개를 넘어가면 각 줄마다 배치해도 해결되지 않으므로 불가능합니다.
짝수일 때는 홀수를 처리할 수 없습니다.
홀수의 개수가 홀수일 때 N이 홀수가 아니면 처리할 수 없습니다. (남는 홀수가 발생하기 때문입니다)