최소·최대 제거 게임에서 마지막에 남는 숫자 찾기 (C++)

문제 설명

n개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. 판 위에 n개의 숫자가 적혀 있고, 아말(Amal)과 비말(Bimal)이 번갈아 가며 턴제 게임을 진행합니다. 각 턴마다 두 사람은 숫자 하나를 골라 판에서 제거합니다. 아말이 먼저 시작하며, 아말은 마지막까지 남는 숫자를 최소화하려고 하고, 비말은 이를 최대화하려고 합니다. 우리가 구해야 할 것은 최종적으로 판에 남게 되는 숫자입니다.

예를 들어 입력이 A = [2, 1, 3]이라면 결과는 2가 됩니다. 아말이 먼저 3을 제거하고, 비말이 1을 제거하면 최종적으로 2만 남기 때문입니다.

풀이 접근 방법

이 문제의 핵심은 배열을 정렬한 뒤 중앙에 해당하는 원소를 반환하는 것입니다. 그 이유는 다음과 같습니다.

• 아말(최소화 플레이어)은 자신의 턴에 남아 있는 수 중 가장 큰 값을 제거하는 것이 최선입니다.
• 비말(최대화 플레이어)은 자신의 턴에 남아 있는 수 중 가장 작은 값을 제거하는 것이 최선입니다.
• 이 과정이 반복되면 양쪽 끝의 숫자부터 차례로 사라지고, 결국 정렬된 배열의 중앙 원소만 남게 됩니다.

따라서 다음 단계로 문제를 해결할 수 있습니다.

n := A의 크기
배열 A를 오름차순으로 정렬
return A[⌊(n - 1) / 2⌋]

C++ 구현 예제

아래 코드를 통해 더 쉽게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
    int n = A.size();
    sort(A.begin(), A.end());
    return A[(n - 1) / 2];
}
int main(){
    vector<int> A = { 2, 1, 3 };
    cout << solve(A) << endl;
}

입력

{ 2, 1, 3 }

출력

2