1360-C, *1100

Problem - 1360C - Codeforces

문제

• 두 자연수 $a$, $b$가 닮았다($a\sim b$)는 것을 다음과 같이 정의한다
  $a \sim b \Leftrightarrow a\equiv b\ (mod\ 2)\ or \left | a-b \right |=1$
• 짝수 $n(2\leq n \leq 50)$개의 원소가 주어졌을 때, 닮은 수끼리 모두 짝지을 수 있는가? --- !

 

$O(tn)$

$n$이 짝수 이므로 $n$개의 수를 다음 두 가지 경우 중 하나이다.
i) 짝수가 짝수개, 홀수가 짝수개
ii) 짝수가 홀수개, 홀수가 홀수개

i) 인 경우
짝수는 짝수끼리, 홀수는 홀수끼리 짝지으면 된다. 즉, ! 가 가능하다

ii) 인 경우
$a\equiv b\ (mod\ 2)$ 인 $a$, $b$가 존재한다고 하자. a와 b 를 짝지으면 남은 수들은 (i)과 같은 상태이다
만약 그러한 $a$, $b$가 존재하지 않으면 ! 가 불가능하다

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> v;
        int tmp;
        int cnt_odd = 0;
        while(n--){
            cin >> tmp;
            v.emplace_back(tmp);
            if(tmp%2) cnt_odd++;
        }
 
        cnt_odd %= 2;
        if(cnt_odd){
            sort(v.begin(), v.end());
            int flag = 0;
            for(int i = 0; i < v.size()-1; i++){
                if(abs(v[i]-v[i+1]) == 1) flag = 1;
            }
            if(flag) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        else cout << "YES" << endl;
    }
 
    return 0;
}cs