카드 게임 소스작성.

ㅣ현재 배우고 있는 과목에서 나온 과제다. 처음에 접근을 잘못해서 오류에 빠졌다가 새로이 생각을 고쳐먹고 다시 접근했다.
n숫자 제거하기

¨1~3까지의 수를 임의로 선택하여 아래 6개의 수열을 만든다.

(1, 3, 2, 3, 2, 2)

¨두 사람이 번갈아 가면서 각각 3개의 숫자를 제거한다. 단 제거할 수 있는 숫자는 남아 있는 수 중에서 양 끝에 있는 수이다.

¨각자 제거한 수를 더하여 그 값이 큰 쪽이 이긴다.

¨두 사람은 자신이 승리하기 위해 선택할 수 있는 최선의 방법만 선택한다.

¨먼저 제거하는 사람과 나중에 제거하는 사람 중에서 누가 승리하는가?

¨승패가 어떻게 결정되는지 설명하라.

def P(arr):
    if len(arr) ==  2:
        return max(arr) - min(arr)
    else:
        return max(arr[0] - P(arr[1:]), arr[-1] - P(arr[0:-1]) )

def test(arr):
    res = P(arr)
    if(res == 0) :
        print arr, "배열 일 때 비김."
    else:
        print arr, "배열 일 때, ", P(arr), "차이로 먼저 뽑는 사람이 이김."

test([1,2])
test([1,2,3])
test([3,2,1])
test([3,2,1,2])
test([3,2,1,2,1,2])
test([2,1,2,1,2,3])
test([3,2,1,2,1,2])
test([3,3,3,3,3,3])
test([1,1,1,2,1,1])
test([1,2])
test([1,2,3])
test([3,2,1])
test([3,2,1,2,1,2])
test([3,2,1,3,2,2,1,2])
test([2,1,2,3,3,1,2,3])
test([3,2,1,3, 2, 2,1,2])
test([3,3,3,1,1,3,3])
test([1,1,1,2,3,2,1,1])

---------------------------
if len(arr) ==  2:
        return max(arr) - min(arr)
    else:
        return max(arr[0] - P(arr[1:]), arr[-1] - P(arr[0:-1]) )

이 부분이 핵심 점화식인데,
P(arr) : 들어온 배열에서 최초로 뽑는 사람이 (모든 사람이 최선을 다했을 경우)이기는 차이로 정의
P([1,2]) 라면 처음 뽑는 사람이 2, 다음사람이 1 뽑아서
1 차이로 이김.

이렇게 하면 두개일 때 base 연산이 진행되고 세개 이상일 경우
첫번째 원소를 제거하는쪽이 더 유리한지, 다음 원소를 제거하는 쪽이 더 유리한지, 판단해서 재귀 호출이 이뤄짐.
사실상 정확한 결과를 알고 싶다면 재귀의 끝까지 들어가봐야 결과를 알 수가 있음.
6개인 경우는 사람이 이 알고리즘을 생각할 수는 있지만, 일반적인 개수 n(=짝수) 가 들어올 때는, n 이 8 이상만 되더라도 분기점이 2의 승수로 올라가기 때문에 사람 머리로 이 게임에서 승패가 이뤄지는지는 알 수가 없다.

e.g) P([1,2]) = 1

[1,2,3] 일 때,
1을 선택하고 나머지를 최선을 다들 다 했을 때 이기는 차이는 다음과 같다.
P([1,2,3]) = max(1 - P([2,3], 3 - P[1,2])

[1,2,3,2] 일 때,
1을 선택하고 나머지를 최선을 다들 다 했을 때 이기는 차이는 다음과 같다.
P[1,2,3,2] = max(1 - P[2,3,2], 2 - P[1,2,3])
...

base 연산 두개일 때를 생각해보면 같지 않은 이상 제일 처음뽑는 사람이 이기므로 둘다 최선을 다할 경우, 먼저 뽑는 사람이 이기거나 비긴다.