[DP] 게임을 위한 최적의 전략

본 포스팅은 Aashish Barnwal 에 의해 작성된 여기를 참고로 재구성했습니다.

문제

값이 $v_1, v_2 \cdots v_n$ 인 $n$ 개의 동전들을 일렬로 나열한 테이블을 상상해보자. 이 게임은 1:1 대전으로 상대방과 턴을 돌아가면서 한다. 각 턴에, 턴을 가진 플레이어는 일렬로 나열한 동전 중에서 가장 처음 또는 가장 끝에 있는 동전을 선택하고 가져간다. 가져간 동전은 절대로 테이블 위에 올려놓을 수 없다. 또한 가져간 동전의 값은 해당 턴을 가진 플레이어의 점수로 바뀐다. 당신이 게임에 참가한 플레이어라면 무조건 이기기 위한 최대 값을 만드는 경우의 수를 찾아라. (단, 게임의 시작은 당신이 먼저다.)

참고 : 상대방 역시 당신과 같이 똑똑하며, 최적의 수를 둔다고 가정한다.

이 문제에 대한 연습은 여기서 하실 수 있습니다. 먼저 문제를 풀어보신 뒤에 정답을 보는것을 추천드립니다.

---

정답

문제를 이해하기 위해 간단한 예시를 들겠습니다 :
여기서 먼저 시작하는 사람은 A 라 하고, 상대방은 B라고 지칭하겠습니다.

1. 5, 3, 7, 10 : A는 최대 15(10 + 5) 점을 모을 수 있다.

2. 8, 15, 3, 7 : A는 최대 22(7 + 15) 점을 모을 수 있다.

가설 : 매 턴마다 가장 큰 값을 가지는 동전을 고르면 무조건 이기는거 아닌가요?

사실, 아닙니다. 위의 두번째 예를 다시 살펴보면 이 가설에 대한 반례가 있습니다.

1. $\dotsc$A가 8을 고릅니다.
$\dotsc$B가 15를 고릅니다.
$\dotsc$A가 7을 고릅니다.
$\dotsc$B가 3을 고릅니다.
A 가 모은 총 점수는 15 입니다. (8+7)

2. $\dotsc$A가 7을 고릅니다.
$\dotsc$B가 8를 고릅니다.
$\dotsc$A가 15를 고릅니다.
$\dotsc$B가 3을 고릅니다.
A 가 모은 총 점수는 22 입니다. (7+15)

2번째 전략을 통해서 항상 최고의 값을 가지는 동전을 고르지 않더라도 최대의 점수를 만들 수 있다는것을 아실 수 있을겁니다.

이 게임에서는 두가지 선택이 있습니다:

1. A는 $v_i$ 의 값을 가진 $i$번째 동전을 고릅니다 : B는 $i+1$ 번째 동전을 고르거나 $j$ 번째 동전을 고를 수 있습니다. B는 A 가 최대한 '적은(min)' 값을 가진 동전을 가져가게끔 최적의 동전을 선택하려 할겁니다. 수식으로 표현하자면 이렇습니다.

   A 는 $v_i + min(F(i+2,j),F(i+1,j-1))$ 의 값을 고른다.

   Q. $F(i+2,j)$ 는 왜 이렇고, $F(i+1,j-1)$ 는 뭐죠?
   함수 $F(x,y)$ 는 DP 문제를 풀때 흔히 볼 수 있는 재귀 형태의 함수라고 생각하시면 됩니다. 즉, $x$ 부터 $y$ 번째 까지의 동전이 나열되어 있을때 얻을 수 있는 최대의 점수를 반환하는 함수가 $F(x,y)$ 입니다. $i$ 번째 동전을 A 가 가져가게 된다면 B는 $i+1$ 또는 $j$ 번째 동전을 고르게 되고 다시 A 차례가 되었을때 $i+2$ 또는 $j-1$ 번째의 동전을 고르게 되는 것이죠. ($j$ 가 뒤쪽의 동전이므로 -1 , $i$ 는 앞쪽의 동전이므로 +1)

   

2. A 는 $v_j$ 의 값을 가진 $j$ 번째 동전을 고릅니다 : B는 $j-1$ 번째 동전을 고르거나 $i$ 번째 동전을 고를 수 있습니다. 이 역시도 B는 A 가 최대한 '적은' 값을 가진 동전을 가져가게끔 최적의 동전을 선택하려 할겁니다. 수식으로 표현하자면 이렇습니다.

   A 는 $v_j + min(F(i+1,j-1),F(i,j-2))$ 의 값을 고른다.

   

다음은 위의 두가지 선택을 베이스로 한 재귀적 솔루션 입니다. 이 솔루션에서는 두 선택중 가장 최고의 값을 반환하는것을 선택합니다.

F(i, j)  는 i 번째 동전부터 j 번째 동전까지 A 가 고를때 찾을수 있는 최고의 점수를 반환합니다.

    F(i, j)  = Max(V_i + min(F(i+2, j), F(i+1, j-1) ), 
                   V_j + min(F(i+1, j-1), F(i, j-2) )) 
Base Cases
    F(i, j)  = V_i            If j == i (동전이 하나 뿐일때)
    F(i, j)  = max(V_i, V_j)  If j == i+1 (동전이 두개밖에 없을때)

왜 이 문제에 DP 개념이 포함되나요?

중복되는 서브 문제들이 존재하기 때문입니다. 위에만 보아도, F(i+1,j-1) 가 두번 계산되는것을 볼 수 있습니다.

// 일련의 동전에서 최대값을 찾는 C 프로그램
#include <stdio.h>
#include <limits.h>

// 2개의 정수들중 최대 최소를 찾는 함수
int max(int a, int b)  {    return a > b ? a : b;  }
int min(int a, int b)  {    return a < b ? a : b;  }

// n 크기의 동전의 값이 적힌 배열에서 A 가 찾을 수 있는 최적의 값을 반환하는 함수
// n 은 반드시 짝수여야 한다.
int optimalStrategyOfGame(int* arr, int n)
{
    // 서브 문제들의 솔루션을 저장하기 위한 테이블 생성
    int table[n][n], gap, i, j, x, y, z;

    // 위의 재귀 공식을 통해서 테이블을 채웁니다. 
    // 테이블은 최종 결과값인 table[0][n-1] 까지 대각선 방향으로 채워집니다.
    for (gap = 0; gap < n; ++gap)
    {
        for (i = 0, j = gap; j < n; ++i, ++j)
        {
            // 위의 재귀 공식을 통해서 만든 변수들은 다음과 같습니다.
            // x 는 F(i+2,j) y 는 f(i+1, j-1) 그리고 z 는 F(i, j-2).
            // 동전의 총 갯수는 음수가 될 수 없기 때문에 조건을 달았습니다.
            x = ((i+2) <= j) ? table[i+2][j] : 0;
            y = ((i+1) <= (j-1)) ? table[i+1][j-1] : 0;
            z = (i <= (j-2))? table[i][j-2]: 0;

            table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z));
        }
    }

    return table[0][n-1];
}

// 드라이버 프로그램 (테스트)
int main()
{
    int arr1[] = {8, 15, 3, 7};
    int n = sizeof(arr1)/sizeof(arr1[0]);
    printf("%dn", optimalStrategyOfGame(arr1, n));

    int arr2[] = {2, 2, 2, 2};
    n = sizeof(arr2)/sizeof(arr2[0]);
    printf("%dn", optimalStrategyOfGame(arr2, n));

    int arr3[] = {20, 30, 2, 2, 2, 10};
    n = sizeof(arr3)/sizeof(arr3[0]);
    printf("%dn", optimalStrategyOfGame(arr3, n));

    return 0;
}

출력값

22
4
42

생각해보기

위의 솔루션은 오직 n, 즉, 동전의 갯수가 짝수개여야지 적용 가능한 솔루션입니다. 과연 홀수일때는 어떨까요? 맨 처음 생각한 '양쪽 동전중 가장 큰 값 집기' 가 최적의 수 일까요?

---