[C++] Interview Question : Pots of gold game

| Question 

Pots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot - perfect information). 
They get alternating turns in which the player can pick a pot from one of the ends of the line. 
The winner is the player which has a higher number of coins at the end. The objective is to "maximize" the number of coins collected by A, assuming B also plays optimally. A starts the game.

The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?

At the end I was asked to code this strategy!

 

번역:
두 명의 Player A와 B가 있다. 금화가 들어있는 항아리가 일렬로 주어지고, 각 항아리엔 일정량의 금화가 들어가 있다. 
Player들은 각 항아리에 금화가 몇 개 들어가 있는지 알 수 있다. 이 상태에서 아래와 같은 규칙으로 게임을 진행한다. 
    * 각 Player들은 일렬로 늘어져있는 항아리의 양 끝 중 하나를 선택할 수 있고, 항아리 안의 모든 금화를 가져간다. 
    * 서로 한번씩 번갈아가며 항아리를 선택하는 방식으로 게임을 진행한다.
    * 이 게임에서 승리하려면 최대한 많은 수의 동전을 얻어야 한다.

자 그렇다면, Player A가 게임을 먼저 시작했을 때, A가 이기려면 어떻게 해야 할까? 이를 코드로 구현하라. 
단, Player B도 항상 최선의 선택을 한다고 가정한다. 

---

| Solution

문제를 풀 때 고려한 사항

• 문제 이해하기가 굉장히 난해했다. 애초에 항아리의 금화 개수가 주어지지 않는 문제는 처음이라 시작조차 어려웠다
• 항아리의 금화 개수는 모르는 상태에서 문제를 풀어야 한다. 물론 항아리에 금화가 없는 경우도 있다고 생각하자. 

Method1

문제를 이해하기 위해 손으로 먼저 풀어보았다. 

 

아래와 같이 항아리가 일렬로 있고 n번째 항아리에 n개의 금화가 들어있다고 가정하자. 

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

여기서 게임을 시작한다면 Player A는 0번째 항아리와 10번째 항아리 중 하나를 골라야 한다. 10번째 항아리를 골랐다고 하자.

Player A turn : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, [10]

그렇다면 남은 항아리 중  Player B는 0번째 항아리와 9번째 항아리 중 하나를 골라야 하며, 당연하게도 9번째 항아리를 골라야 할 것이다. 

Player B turn : 0, 1, 2, 3, 4, 5, 6, 7, 8, [9], [10]

이런식으로 게임이 진행된다고 볼 수 있다.

 

위의 풀이 방식은 개발 입장에서도 몇 번째 항아리에 몇 개의 금화가 있는지 안다는 점이고, 해결해야 하는 문제는 몇 번째 항아리에 몇 개의 금화가 들어있는지 모른다는 것이다. 

자 그러면 어떻게 해야 Player A가 이길 수 있으며, B도 최선의 결과를 얻는 코드를 일반화할 수 있을까?

다시 한번 Player A입장에서 생각해보자. 

제일 앞쪽 항아리의 index를 front, 뒤쪽 항아리의 index를 back라고 하였을 때 둘 중 최대 개수가 들어있는 항아리를 선택해야 한다. 

int case_front = pots[front];
int case_back = pots[back];

앞쪽 항아리 혹은 뒤쪽 항아리를 골랐을 때 다음 차례인 player B도 최대한 유리한 경우를 고를 것이고, 그다음 가능한 경우의 수 중 최대를 뽑아야 A가 이길 수 있다. 

예를 들어, 위의 예시를 다시 가져와보자. 

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, [10]

player A가 10을 뽑았다고 하면

0, 1, 2, 3, 4, 5, 6, 7, 8, [9], [10]

player B는 0 혹은 9를 뽑을 수 있다. 하지만 B도 최대한 유리하게 뽑아야 하기 때문에 9를 뽑아야만 한다.  

즉, 그다음 player A 턴 입장에서 생각해봤을 때 (1와 9중에 선택하는 경우, 0과 8중에서 선택하는 경우) 중 최솟값을 뽑아야 B가 자기 자신에게 최대한 유리하게 뽑았다고 결론 내릴 수 있다. 
위의 예시에선 pots의 coin개수가 주어지기 때문에 애초에 B가 9를 뽑는 게 자명하지만 하지만 실제 문제에서는 pots안의 금화 개수를 알 수 없다. 

이를 구현한 코드는 아래와 같다. 

int GetMaxCoin(vector<int> &pots, int front, int back){
    if(front > back) return 0;

    int case_front = pots[front] + min(GetMaxCoin(pots, front + 2, end), GetMaxCoin(pots, front+1, end-1));
    int case_back = pots[back] + min(GetMaxCoin(pots, front, end-2), GetMaxCoin(pots, front+1, end-1));

    return max(case_front, case_back);
}

• Time Complexity : O(4ⁿ) 
• Spcae Complexity : O(1)

한번 호출에 함수 4번을 다시 호출하기 때문에 시간복잡도가 굉장히 놉다. 추가로 줄일 수 있는 방법을 찾아야 할 것 같다. 

To be Continue..