안녕하세요.

오늘은 여기 오시는 분들을 위해 퀴즈 하나를 내려고 해요..

심심할때 한번 풀어보아요..

 quiztitle

 

 

 

 

 

 

 

 

– 문제 –

 

어느날 정희와 보람이는 카드뽑기 게임을 하였습니다.

임의의 숫자가 적혀있는 짝수개의 카드가 일렬로 나열되어 있습니다.

정희와 보람이는 번갈아 가면서 카드 한장씩을 뽑는데..

오른쪽 끝에 있는 카드 또는 왼쪽 끝에있는 카드만 뽑을 수 있습니다.

모든 카드를 다 뽑았을 때, 자신이 뽑은 카드의 숫자의 합이 큰 사람이 이기는 게임입니다.

정희가 먼저 시작한다고 했을 때, 정희는 보람이를 몇점 차이로 이길까요?

단, 정희와 보람이는 항상 자신의 베스트 전략을 사용합니다.

(자신의 점수를 최대화하고 상대방의 점수를 최소화 하는 전략)

 

예1)   10   8   9   12

 

Step 0:   10   8   9   12   (정희:  0점, 보람: 0점)

Step 1:   10   8   9   12   (정희: 12점, 보람 : 0점)

Step 2:   10   8   9   12   (정희: 12점, 보람: 10점)

Step 3:   10   8   9   12   (정희: 21점, 보람: 10점)

Step 4:   10   8   9   12   (정희: 21점, 보람: 18점)

 

빨간색이 현재 플레이어가 가져가는 카드입니다.

위 예제에서는 정희가 보람이를 3점 차이로 이기네요.

 

왠지 자신의 차례에 무조건 큰 수가 적혀있는 카드를 뽑는게 유리해 보입니다.

그런데 다음 예제를 또 보죠.

 

예2)   3   2   10   4

 

정희는 처음에 4 대신 3을 뽑아야 이길 수 있습니다.

Greedy 접근법이 항상 최적의 전략은 아니군요.

 

그럼 여기서 문제..~~

다음 16장의 카드가 차례로 놓여있을 때, 정희는 보람이를 몇점 차이로 이길까요?

10   16   8   16   10   5   8   11   16   6   12   13   9   16   10   10

 

여기서부터 해법입니다.  SPOILER 주의!!

.

.

.

.

.

.

.

.

.

.

 

card(i) = i번째 카드에 적혀있는 수

best(i, j) = i번째 카드에서부터 j번째 카드까지 남아있을 때, 현재 플레이어가 얻을 수 있는 최대 점수 차이

(단, 0 <= i <= j < n)

라고 합시다.

 

현재 플레이어는 i번째(왼쪽 끝) 카드 또는 j번째(오른쪽 끝) 카드를 가져갈 수 있습니다.

만약에  i번째 카드를 뽑았다면, i번째 카드를 얻고 (i+1, j) 상태를 상대방에게 넘겨주게 됩니다.

마찬가지로 j번째 카드를 뽑았다면, j번째 카드를 얻고 (i, j-1) 상태를 상대방에게 넘겨주게 됩니다.

이 두가지 경우중에 더 좋은 경우를 선택해야 합니다.

 

따라서, 다음과 같은 recurrence relation을 얻을 수 있습니다.

 best(i, j) = max(card(i) - best(i+1, j), card(j) - best(i, j-1))

 

이 해법을 C 언어로 구현해 보았습니다.

 

#include <stdio.h>
int card[16] = {
    10, 6, 8, 16, 10, 5, 8, 11, 16, 6, 12, 13, 9, 16, 10, 10
};
int n = 16;

int best(int u, int v)
{
    int result1;
    int result2;

    if (u > v)
    {
        return 0;
    }
    else
    {
        result1 = card[u] - best(u+1, v);
        result2 = card[v] - best(u, v-1);
    }
    return result1 > result2 ? result1 : result2; 
}

int main()
{
    printf(”%d\n”, best(0, n-1));
    return 0;
}

답은 8이 나오네요.. ㅋ

 

이 코드는 올바른 해를 구하기는 하지만,

같은 상태공간을 여러번 계산하는 매우 비효율적인 코드입니다.

이를 보완하기 위해 Memoization 기법을 적용할 수 있습니다.

Memoization에 대해서는 다음 기회에 또 포스팅 하고자 합니다. ^^