백준 17965 (Absolute Game) c++

문제

17965번: Absolute Game

A와 B에게 길이가 같은 배열이 주어지면 A와 B는 서로 한번씩 배열의 숫자 1개를 제거할 수 있습니다.

가지고 있는 배열 중 마지막 원소 1개를 제외하고는 모두 제거 할 수 있는데

A는 마지막 남은 원소들의 차이를 가장 크게 만들려하고

B는 마지막 남은 원소들의 차이를 가장 작게 만들려고 합니다.

A와 B가 게임을 했을 때 마지막 남은 원소의 차이를 출력하는 문제 입니다.

 

A가 먼저 숫자를 제거하고 B가 나중에 제거하게 되므로 결국 선택권은 B한테 있습니다.

따라서 먼저 B의 입장에서 A의 각각의 원소마다 B의 원소와 최소의 차이를 보이는 원소끼리 선을 그을 수 있습니다.

예를 들어 A={2, 14, 7, 14} , B={5, 10, 9, 22} 일 때 B의 입장에서 A의 원소에 따르는 최소차이를 보고 B의 원소와

연결선을 그릴 수 있습니다. 

A가 먼저 임의의 숫자를 지울 수 있으므로 어떤 수를 지우더라도 B는 지워진 숫자와 연결된 B의 원소를 지우게 되면

차이를 최소한으로 만들면서 게임을 진행할 수 있습니다.

즉 B는 연결선이 안 그려진 원소들만 지우면 됩니다.

A의 입장에서도 이러한 전략을 알기 때문에 최소 차이인 (7, 9) 부터 먼저 없앨 것입니다. 

그러다 보면 결국 원소가 연결된 차이중에서 가장 큰 차이가 마지막에 남게 됩니다. (14, 10)

---

전체 코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    vector<ll>A(n), B(n);
 
    for (int i = 0; i < n; i++)
        cin >> A[i];
    for (int i = 0; i < n; i++)
        cin >> B[i];
 
    ll ans = -1e12;
    for (int i = 0; i < n; i++) {
        ll x = 1e12;
        for (int j = 0; j < n; j++) {
            x = min(x, abs(A[i] - B[j]));
        }
        ans = max(ans, x);
    }
    cout << ans;
    return 0;
}