[Codeforeces] Submission Bait [C++]

 

 

#문제 간단 정리

 

mx는 처음에 0으로 주어진다

배열에서 고르면 그 고른 값으로 mx 가 결정되고

상대방에 턴에는 mx 이상인 값만 고를 수 있다.

 

alice 가 이길 수 있는지 없는지 리턴하라는 문제

 

 

 

#문제 해결 방법

요지는 모든 숫자를 카운팅 소트를 해준 다음에

모두가 짝수로 존재한다면 패배하고

홀수개수가 존재한다면 승리한다

 

왜냐하면 일단 가장 높은 숫자의 개수가 짝수개라면

먼저 선택하지 않고 

홀수 개수를 먼저 선택하면 이길 수 있기 때문

5

3 3 3 4 4

일때 3 을 먼저 선택하면 이길 수 있다

만약 가장 높은 숫자가 홀수개라면 그냥 이길 수 있다

6

3 3 3 4 4 4

 

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
 
    while (t--) {
 
        //첫턴에 mx를 설정 가능하고, 모든 값들이 mx 이하라면 승리
        //현재 가장 높은게 홀수개라면 승리 짝수개라면 패배
 
        int n;
        cin >> n;
 
        vector<int> counting(10002, 0);
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
 
        for (auto i : a) {
            counting[i]++;
        }
 
        vector<int> compress;
 
        for (int i = 10001; i > 0; i--) {
            if (counting[i] != 0) {
                compress.push_back(counting[i]);
            }
        }
 
        bool win = false;
        for (auto i : compress) {
            if (i % 2 == 0) {
            }
            else {
                win = true;
            }
        }
 
 
        if (win) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
 
    return 0;
}