백준 16882 카드게임 (C++)

https://www.acmicpc.net/problem/16882

16882번: 카드 게임

게임이론 문제입니다. 게임이론 문제들은 제 경험상 손으로 써가면서 경우의 수를 찾는게 가장 좋더라고요. 

생각보다 직관적이어서 어렵지 않은 문제였습니다.

어떤 수를 가져가면 그보다 작은 수 들을 전부 없애고 마지막으로 카드를 전부 없앤 사람이 이기는 게임입니다.

 

직관적으로 가장 큰 수를 가져가게되면 큰 수를 제외한 모든 수를 가져갈 수 있게되고 따라서 가장 큰 수의 개수가 승리와 연관이 되있다는걸 알 수 있습니다.

 

먼저 홀수일때는 당연히 koosaga가 이기는걸 알 수 있습니다. 가장 큰 수를 집는 걸 반복하게되면 선턴인 koosaga가 당연히 이기게 됩니다.

 

짝수일때도 koosaga가 이기는 방법이 있습니다. 위에서 말했듯이 가장 큰 수를 홀수개일때 집기만 하면 이기게 되는 게임입니다. 그렇다면 두번째로 큰수를 집어서 가장 큰수만 남기고 다 없애게 된다면

결국 cubelover는 어쩔수없이 가장 큰 수를 집어서 홀수개만 남게됩니다. 

 

그렇다면 cubelover가 이기는 경우의수는 모든 수가 같아서 가장 큰 수밖에 없어서 koosaga가 어쩔수없이 가장 큰수를 집어 홀수개로 만드는 경우의수겠죠.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int main(){
    fast_io();
    int solve=0;
    int ans=0;
    int N;
    cin>>N;
    for(int x=0;x<N;x++){
        int input;
        cin>>input;
        if(solve<=input){
            if(solve==input){
                ans++;
                continue;
            }
            solve=input;
            ans=1;
        }
    }
    if(ans==1){
        cout<<"koosaga";
    }
    else{
        if(N-ans==0 && ans%2==0){
            cout<<"cubelover";
        }
        else{
            cout<<"koosaga";
        }
    }
}