백준 11968 High Card Wins (USACO December 2015 Silver 2번)

문제 링크: https://www.acmicpc.net/problem/11968

11968번: High Card Wins

E: 1 2 5 8 10
B: 3 4 6 7 9

처음 세판은 B 가 이긴다(3 > 1, 4 > 2, 6 > 5). 그 다음 B가 가진 7로 이길수 있는 카드가 없으므로 버리고, 다음 카드 9로 E가 가지고 있는 8을 이길수 있으므로, 최종적으로 B가 4번 이길수 있음.

E 와 B가 각각 가진 카드들은 벡터에 입력받고, 앞에서부터 B가 이기면 답을 1 증가시키고, B와 E 둘다 사용한 카드를 버리고 다음 카드로 index를 옮겨준다. B가 지면 답을 증가시키지 않고, 현재 B가 진 카드는 쓸모가 없으므로 버리고 B만 다음 카음 카드로 index를 옮겨주면 됨.

#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 5e4;
int N, cards[2 * MAX + 1], ans, b, e;
vector<int> B, E;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    for(int i = 0; i < N; i++) {
        int num;
        cin >> num;
        cards[num] = 1;
    }
    for(int i = 1; i <= 2 * N; i++) {
        if(cards[i]) E.push_back(i);
        else B.push_back(i);
    }
 
    while(b < N && e < N) {
        if(B[b] > E[e]) {
            ans++;
            e++;
            b++;
        }
        else b++;
    }
 
    cout << ans << '\n';
    return 0;
}