Ruby

이건 lambda로 한줄에 푸는 방법이고,

m=->p{p.to_a.empty? ? 0:[p[0]+[m[p[2..-1]],m[p[1..-2]]].min,p[-1]+[m[p[1..-2]],m[p[0..-3]]].min].max}

정리하면 아래와 같습니다.

def maximize(pots)
  return 0 if pots.to_a.empty? 

  [pots[0] + [maximize(pots[2..-1]), maximize(pots[1..-2])].min, 
    pots[-1] + [maximize(pots[1..-2]), maximize(pots[0..-3])].min].max
end

각각 앞과 뒤를 선택했을 때의 동전과 그 이후로 얻을 수 있는 최소한의 이익이 더 큰 것을 재귀적으로 계산해서, 더 큰 쪽을 선택하는 방법입니다. 결과는 최종적인 A의 점수입니다.

Clojure 코드입니다.

(defn pots-of-gold-games [& pots]
  (let [eval-kwd  (fn [k & params]
                    (apply (-> k name symbol eval) params))
        pop-pots  (fn [pots choice]
                    (if (= choice :first)
                      (rest pots)
                      (butlast pots)))
        ->korean  {:first "앞" :last "뒤"}
        print-log (fn [{name :name} pots choice]
                    (println name "가"
                             (choice ->korean) "에서"
                             (eval-kwd choice pots) "만큼 꺼낸다."
                             "\t남은 금:" pots "->" (pop-pots pots choice)))
        print-sco (fn [{:keys [name score choices]}]
                    (println name "점수:" score "\t선택:" (map ->korean choices)))
        take-gold (fn [player pots choice]
                    (print-log player pots choice)
                    (-> player
                        (assoc :score (+ (:score player) (eval-kwd choice pots))) 
                        (assoc :choices (conj (:choices player) choice))))
        choose    (fn [pots]
                    (if (or (= 1 (count pots))
                            (<= (- (last pots) (-> pots butlast last))  
                                (- (first pots) (second pots))))
                      :first
                      :last))
        continue  (fn [a b pots turn]
                    (if (empty? pots)
                      [a b]
                      (let [choice (choose pots)]
                        (if (= :a turn)
                          (recur (take-gold a pots choice) b (pop-pots pots choice) :b)
                          (recur a (take-gold b pots choice) (pop-pots pots choice) :a)))))
        result    (continue {:name "A" :score 0, :choices []}
                            {:name "B" :score 0, :choices []}
                            pots
                            :a)]
    (println "--------------------------------------------------------")
    (print-sco (first result))
    (print-sco (second result))))

테스트 결과:

(pots-of-gold-games 1 2)
A 가 뒤 에서 2 만큼 꺼낸다.  남은 금: (1 2) -> (1)
B 가 앞 에서 1 만큼 꺼낸다.  남은 금: (1) -> ()
--------------------------------------------------------
A 점수: 2     선택: (뒤)
B 점수: 1     선택: (앞)

(pots-of-gold-games 9 8 7 5 4 6 3 1 2)
A 가 앞 에서 9 만큼 꺼낸다.  남은 금: (9 8 7 5 4 6 3 1 2) -> (8 7 5 4 6 3 1 2)
B 가 앞 에서 8 만큼 꺼낸다.  남은 금: (8 7 5 4 6 3 1 2) -> (7 5 4 6 3 1 2)
A 가 앞 에서 7 만큼 꺼낸다.  남은 금: (7 5 4 6 3 1 2) -> (5 4 6 3 1 2)
B 가 앞 에서 5 만큼 꺼낸다.  남은 금: (5 4 6 3 1 2) -> (4 6 3 1 2)
A 가 뒤 에서 2 만큼 꺼낸다.  남은 금: (4 6 3 1 2) -> (4 6 3 1)
B 가 앞 에서 4 만큼 꺼낸다.  남은 금: (4 6 3 1) -> (6 3 1)
A 가 앞 에서 6 만큼 꺼낸다.  남은 금: (6 3 1) -> (3 1)
B 가 앞 에서 3 만큼 꺼낸다.  남은 금: (3 1) -> (1)
A 가 앞 에서 1 만큼 꺼낸다.  남은 금: (1) -> ()
--------------------------------------------------------
A 점수: 25    선택: (앞 앞 뒤 앞 앞)
B 점수: 20    선택: (앞 앞 앞 앞)

(pots-of-gold-games 1 3 4 5 1)
A 가 앞 에서 1 만큼 꺼낸다.  남은 금: (1 3 4 5 1) -> (3 4 5 1)
B 가 앞 에서 3 만큼 꺼낸다.  남은 금: (3 4 5 1) -> (4 5 1)
A 가 앞 에서 4 만큼 꺼낸다.  남은 금: (4 5 1) -> (5 1)
B 가 앞 에서 5 만큼 꺼낸다.  남은 금: (5 1) -> (1)
A 가 앞 에서 1 만큼 꺼낸다.  남은 금: (1) -> ()
--------------------------------------------------------
A 점수: 6     선택: (앞 앞 앞)
B 점수: 8     선택: (앞 앞)

A와 B가 각자 자신에게 가장 큰 이익이 되면서 상대방에게 가장 적은 이익이 되도록 하는 수를 취하는 전략을 쓰도록 했습니다.

필승 전략은 아닙니다. B가 이길 수밖에 없는 상황이 있기 때문입니다.

B가 이기는 경우는 각자 갖고 있는 점수를 역전할 수 있는 수가 마지막에 남게되는 경우인데요. 그 수를 A가 빨리 취할 수 있는 경우라면 A가 이기게 되지만, 아닌 경우에는 A가 B가 그 수를 먹지 못하도록 견제하다가 마지막에 그 수가 남게 됩니다.

이런 경우에는 어떤 순서로 금을 취하더라도 A가 이길 수는 없더군요.

제가 테스트해본 결과는 이렇습니다만 "이게 맞다", "왜 그렇다"하고 증명은 못하겠네요... 찝찝해요.

틀렸을 수도 있으니 지적 환영합니다. ㅎㅎㅎ

P.S.

nacyot 님이 올린 알고리즘을 Clojure 코드로 옮겨 보았습니다.

(defn maximize [pots]
  (if (empty? pots)
    0
    (let [left-first  (+ (first pots)
                         (min (maximize (rest (rest pots)))
                              (maximize (butlast (rest pots)))))
          right-first (+ (last pots)
                         (min (maximize (rest (butlast pots)))
                              (maximize (butlast (butlast pots)))))]
      (max left-first right-first))))

결과값은 위에 쓴 코드와 같네요.

아, 이 문제는 정말 재귀의 끝판왕이라고 해도 될 것 같습니다.

제가 푼 것은 아니고 nacyot님의 풀이를 파이썬으로 재 구성한 후 분석 해 본 것입니다.

주석을 친절하게 달았으니 nacyot님의 풀이가 어려우신 분들은 좀 더 편하게 보실 수 있을 것 같네요 ^^

# -*- coding: utf-8 -*-

def maximize(pots):
    if not pots: return 0

    # A가 먼저 좌측을 선택할 경우
    choose_leftmost = pots[0]

    # B는 최적의 선택을 하므로 그 다음 A가 B이후에 가질 수 있는 값은
    # -> B가 좌측을 선택하고 남은 항아리들의 maximize값
    # -> B가 우측을 선택하고 남은 항아리들의 maximize값
    # 위 둘 중 작은 값을 가져야만 한다.
    # 왜냐하면 B가 최선의 선택을 하기 때문에 A는 둘 중에 작은 값을 가질 수 밖에 없다.
    next_choose_left = maximize(pots[2:])       # a가 좌측, b가 좌측선택
    next_choose_right = maximize(pots[1:-1])    # a가 좌측, b가 우측선택
    next_value = min(next_choose_left, next_choose_right)

    # 두 값을 더한다.
    left_case = choose_leftmost + next_value

    # 이번에는 A가 우측을 선택할 경우
    choose_rightmost = pots[-1]

    # 위와 마찬가지 경우이므로 설명 생략
    next_choose_left = maximize(pots[1:-1])     # a가 우측, b가 좌측
    next_choose_right = maximize(pots[0:-2])    # a가 우측, b가 우측
    next_value = min(next_choose_left, next_choose_right)

    # 두 값을 더한다.
    right_case = choose_rightmost + next_value

    # 최종적으로 둘중에 큰값을 리턴한다.
    return max(left_case, right_case)


print maximize([9,8,7,5,4,6,3,1,2])
print maximize([1,3,4,5,1])

p.s. 아 추가로 A가 선택한 항아리들만 추려서 출력을 해 보려고 했는데, 이 또한 쉽지 않네요.. 이것이 가능한지는 모르겠지만 이 또한 하나의 도전과제라고 생각합니다.

from random import randint
Li,A,B=[],0,0
for i in range(20):
    Li.append(randint(1,7))
print Li #original jar

sack=[]  #A,B가 고른 항아리를 순서대로 담은 자루
def greed():
    if Li[0]+Li[2]>= Li[-1]+ Li[-3]:
        sack.append(Li[0]);Li.remove(Li[0])
    else:
        sack.append(Li[-1]); Li.pop()
    if len(Li)>=4:
        greed()
    else:
        for i in Li:
            sack.append(i)
        return sack
greed()
for i in range(len(sack)):
    if i%2==0:
        A+= sack[i]  #Sack에 순서대로 담았으니 인덱스가 짝수인 것이 A꺼
    else:
        B+= sack[i]
print sack; print "A= %d, B= %d" %(A,B)

음 다양한 풀이가 이미 나와서 별 의미는 없지만 길가의풀 님께서 관심을 가지실지도 몰라 A, B 따로구한 Python코드를 작성해 봤네요.

def greedy(pots):
    if not pots : return 0
    return max(pots[0]+min(greedy(pots[2:-1]),greedy(pots[1:-2])),pots[-1]+min(greedy(pots[1:-2]),greedy(pots[0:-3])))
numofpot=input("항아리의 갯수?")
pot=[]
for i in range(1,int(numofpot)+1):
    gold=input("%d번째 항아리의 금화 갯수?"%i)
    pot+=[int(gold)]
print(pot)
suma=0
sumb=0
for i in range(1,int(numofpot)+1):
    if(i%2==1):
        if pot[0]+min(greedy(pot[2:-1]),greedy(pot[1:-2]))>=pot[-1]+min(greedy(pot[1:-2]),greedy(pot[0:-3])):
            print("A의 선택=%d"%pot[0])
            suma+=pot[0]
            del pot[0]
            if not pot : print("완료!")
            else : print(pot)
        else:
            print("A의 선택=%d"%pot[-1])
            suma+=pot[-1]
            del pot[-1]
            if not pot : print("완료!")
            else : print(pot)
    else:
        if pot[0]+min(greedy(pot[2:-1]),greedy(pot[1:-2]))>=pot[-1]+min(greedy(pot[1:-2]),greedy(pot[0:-3])):
            print("B의 선택=%d"%pot[0])
            sumb+=pot[0]
            del pot[0]
            if not pot : print("완료!")
            else : print(pot)
        else:
            print("B의 선택=%d"%pot[-1])
            sumb+=pot[-1]
            del pot[-1]
            if not pot : print("완료!")
            else : print(pot)
print("A의 최적점수=%d"%suma)
print("B의 최적점수=%d"%sumb)

처음에 잘 이해가 잘 안가서 시뮬레이션 하는걸 만들어 봤습니다. 이제 좀 이해가 가네요. 항아리의 갯수가 많아지면 계산횟수가 너무 많아지는게 단점입니다...

잘 놀았슴다. 휴우 정말 어려운 문제군요..

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            var pogg = new PotsOfGoldGame(10);

            var gameResult = pogg.Run();

            int maxCoins = gameResult.MaxCoins;

            Console.WriteLine("pogg.Pots = [" + string.Join(",", pogg.Pots) + "]");
            Console.WriteLine(string.Join("\n", gameResult.Progress.Reverse<string>()));
            Console.WriteLine("A's coins: {0}", maxCoins);
            Console.WriteLine("B's coins: {0}", pogg.Pots.Sum() - maxCoins);
            Console.ReadKey();
        }
    }

    public enum Order
    {
        First, Second
    }

    public class PotsOfGoldGame
    {
        public List<int> Pots = new List<int>();

        public int Count { get; } = 0;

        public PotsOfGoldGame(int count)
        {
            int ticks = (int)DateTime.Now.Ticks;

            Random r = new Random(ticks);

            for (int i = 0; i < count; i++)
            {
                Pots.Add(r.Next() % 8 + 1);
            }

            Count = count;
        }

        public GameResult Run()
        {
            return Run(Pots.ToList<int>(), Order.First);
        }

        private GameResult Run(List<int> list, Order order)
        {

            string listStr = string.Join(",", list.ToArray());
            #region uni
            if (list.Count == 1)
            {
                switch (order)
                {
                    case Order.First:
                        var uniFirst = new GameResult() { MaxCoins = list[0] };
                        uniFirst.Progress.Add(
                            "B : Head(" + list[0] + ") [" + listStr + "]");
                        return uniFirst;
                    case Order.Second:
                        var uniSecond = new GameResult() { MaxCoins = 0 };
                        uniSecond.Progress.Add(
                            "B : Head(" + list[0] + ") [" + listStr + "]");
                        return uniSecond;
                    default:
                        throw new Exception("invalid order.");
                }
            }
            #endregion

            //headLess
            int head = list[0];
            var headLessList = GetHeadLessList(list);
            var headLessSecondResult = Run(headLessList, Order.Second);
            var headSum = head + headLessSecondResult.MaxCoins;

            //tailLess
            int tail = list[list.Count - 1];
            var tailLessList = GetTailLessList(list);
            var tailLessSecondResult = Run(tailLessList, Order.Second);
            var tailSum = tail + tailLessSecondResult.MaxCoins;

            switch (order)
            {
                case Order.First:
                    if (headSum > tailSum)
                    {
                        var headResult = new GameResult();
                        headResult.MaxCoins = headSum;
                        headResult.Progress = headLessSecondResult.Progress.ToList<string>();
                        headResult.Progress.Add("A : Head(" + head + ") [" + listStr + "]");
                        return headResult;
                    }
                    else
                    {
                        var tailResult = new GameResult();
                        tailResult.MaxCoins = tailSum;
                        tailResult.Progress = tailLessSecondResult.Progress.ToList<string>();
                        tailResult.Progress.Add("A : Tail(" + tail + ") [" + listStr + "]");
                        return tailResult;
                    }
                case Order.Second:
                    if (headSum > tailSum)
                    {
                        var headlessFirstResult = Run(headLessList, Order.First);
                        headlessFirstResult.Progress.Add(
                            "B : Head(" + head + ") [" + listStr + "]");
                        return headlessFirstResult;
                    }
                    else
                    {
                        var taillessFirstResult = Run(tailLessList, Order.First);
                        taillessFirstResult.Progress.Add(
                            "B : Tail(" + tail + ") [" + listStr + "]");
                        return taillessFirstResult;
                    }
                default:
                    throw new Exception("invalid order.");
            }
        }

        private List<int> GetHeadLessList(List<int> list)
        {
            var result = list.ToList<int>();
            result.RemoveAt(0);
            return result;
        }

        private List<int> GetTailLessList(List<int> list)
        {
            var result = list.ToList<int>();
            result.RemoveAt(result.Count - 1);
            return result;
        }
    }

    public class GameResult
    {
        public int MaxCoins { get; set; } = 0;
        public List<string> Progress = new List<string>();
    }
}

pogg.Pots = [7,8,4,2,6,2,2,4,3,4]
A : Tail(4) [7,8,4,2,6,2,2,4,3,4]
B : Head(7) [7,8,4,2,6,2,2,4,3]
A : Head(8) [8,4,2,6,2,2,4,3]
B : Head(4) [4,2,6,2,2,4,3]
A : Tail(3) [2,6,2,2,4,3]
B : Tail(4) [2,6,2,2,4]
A : Tail(2) [2,6,2,2]
B : Tail(2) [2,6,2]
A : Tail(6) [2,6]
B : Head(2) [2]
A's coins: 23
B's coins: 19

단순 DP입니다. 시간/공간복잡도가 O(n^2)이기 때문에 n=1000인 경우까지도 무리없이 계산할 수 있습니다. djmax[i][j] = i~j까지 금화를 선택할 수 있는 상황에서, A가 B보다 얻을 수 있는 점수차이의 최대값 djmin[i][j] = i~j까지 금화를 선택할 수 있는 상황에서, A가 B보다 얻을 수 있는 점수차이의 최소값 이렇게 정의하면, djmax[i][j] = max(djmin[i+1][j] + a[i], djmin[i][j-1] + a[j]) djmin[i][j] = min(djmax[i+1][j] - a[i], djmax[i][j-1] - a[j]) 이 되게 됩니다. 만약 A가 i번 금화를 가져간 경우, 턴은 B에게 넘어가게 되고 B는 djmin[i+1][j] 결과값에 따라 움직이는 것이 최선일 것입니다. A가 j를 가져간 경우도 마찬가지. 이와 같은 원리를 이용해서 A가 얻는 값의 최대를 얻어낼 수 있고, 어떤 순서대로 금화를 선택했는지도 함께 알아낼 수 있습니다.

이렇게 많은 풀이들중에 반복문을 이용한 DP가 하나도 없길래 추가해봤습니다...

#include<stdio.h>
#include<random>
int n;
int a[1009] = { 9, 8, 7, 5, 4, 6, 3, 1, 2 };
int djmax[1009][1009];
int djmax_path[1009][1009];
int djmin[1009][1009];
int djmin_path[1009][1009];
int main()
{
    int i, j, k;
    //n = 9;
    n = 1000;
    for (i = 0; i < n; i++) {
        static std::mt19937 rnd;
        a[i] = rnd()%10000 + 1;
    }
    int score_sum = 0;
    for (i = 0; i < n; i++) {
        djmax[i][i] = a[i];
        djmin[i][i] = -a[i];
        djmax_path[i][i] = 0;
        djmin_path[i][i] = 0;
        score_sum += a[i];
    }
    for (k = 1; k < n; k++) {
        for (i = 0; i + k < n; i++) {
            j = i + k;
            //update djmax
            if (djmin[i + 1][j] + a[i] < djmin[i][j - 1] + a[j]) {
                djmax[i][j] = djmin[i][j - 1] + a[j];
                djmax_path[i][j] = 1;
            }
            else {
                djmax[i][j] = djmin[i + 1][j] + a[i];
                djmax_path[i][j] = 0;
            }
            //update djmin
            if (djmax[i + 1][j] - a[i] > djmax[i][j - 1] - a[j]) {
                djmin[i][j] = djmax[i][j - 1] - a[j];
                djmin_path[i][j] = 1;
            }
            else {
                djmin[i][j] = djmax[i + 1][j] - a[i];
                djmin_path[i][j] = 0;
            }
        }
    }

    printf("A score : %d, B score : %d\n", (score_sum + djmax[0][n - 1]) / 2, (score_sum - djmax[0][n-1])/2);
    /* Trace Path */
    int pi, pj, pk;
    pi = 0; pj = n - 1;
    pk = 0;
    int score_a = 0;
    int score_b = 0;
    while (pi <= pj) {
        printf("{ ");
        for(i=pi; i<=pj; i++)
            printf("%d ", a[i]);
        printf("}\n");
        if (pk == 0) {
            if (djmax_path[pi][pj] == 0) {
                score_a += a[pi];
                printf("A select %d / %d vs %d\n", a[pi], score_a, score_b);
                pi++;
            }
            else {
                score_a += a[pj];
                printf("A select %d / %d vs %d\n", a[pj], score_a, score_b);
                pj--;
            }
        }
        else {
            if (djmin_path[pi][pj] == 0) {
                score_b += a[pi];
                printf("B select %d / %d vs %d\n", a[pi], score_a, score_b);
                pi++;
            }
            else {
                score_b += a[pj];
                printf("B select %d / %d vs %d\n", a[pj], score_a, score_b);
                pj--;
            }
        }
        pk ^= 1;
    }
}

C#으로 작성했습니다. 길가의 풀 님께서 말씀하신 것과 같이 재귀 함수의 끝판왕인듯 싶습니다. 꽤 시간을 많이 소비해서 완성했습니다. 처음에 항아리 갯수를 받고 각 항아리마다 금이 들어갈 수 있는 최대의 수를 입력 받도록 설정했습니다. 항아리 갯수 짝수 체크는 따로 하지 않았습니다. 랜덤으로 완성된 항아리 list를 binary tree에 집어 넣었습니다. 예를 들어 { 3, 9, 1, 2 } 이렇게 항아리가 있으면, 0의 좌우는 3과 2, 3의 좌우는 9와 2, 2의 좌우는 3과 1. binary tree까지 완성을 시키고 이제 본격적인 게임에 들어갑니다. 매 턴마다 playerA든, playerB든, 좌 또는 우를 선택했을 때 이길 수 있는 확률이 높은 쪽으로 선택하도록 설정했습니다. 매 턴마다 얼마의 gold를 확보하는지 알려줍니다. 게임이 끝난 후에 누가 이겼는지 알려줍니다. 굳이 binary tree를 쓸 필요는 없지만, algorithm이 복잡해져 제 머리까지 복잡해지는 것을 피하고자 항아리 안의 금의 숫자를 binary tree로 묶었습니다.

using System;
using System.Collections.Generic;

        public class Node<T> where T : IComparable
        {
            private T data;
            public Node<T> Left, Right;

            public Node(T item)
            {
                data = item;
                Left = null;
                Right = null;
            }

            public T Data
            {
                get { return data; }
                set { data = value; }
            }
        }

        public List<int> InitializeList(int n, int gold)
        {
            var random = new Random();
            var inputs = new List<int>();
            for (int i = 0; i < n; i++) inputs.Add(random.Next(gold + 1));
            return inputs;
        }

        public void InitializeNode(List<int> inputs, Node<int> pots, int left, int right)
        {
            if (left > right) return;
            pots.Left = new Node<int>(inputs[left]);
            pots.Right = new Node<int>(inputs[right]);
            InitializeNode(inputs, pots.Left, left + 1, right);
            InitializeNode(inputs, pots.Right, left, right - 1);
        }

        public void PrintPotsOfGoldGame(Node<int> pots, int playerA = 0, int playerB = 0, bool turn = true)
        {
            if (pots.Left == null && pots.Right == null)
            {
                if (playerA > playerB) Console.WriteLine("Player A won the game.");
                else Console.WriteLine("Player B won the game.");
                return;
            }
            var left = Optimize(pots.Left);
            var right = Optimize(pots.Right);
            if (turn)
            {
                playerA += left > right ? pots.Left.Data : pots.Right.Data;
                if (left > right)
                    Console.WriteLine("Player A has taken left. A has " + playerA + " golds.");
                else Console.WriteLine("Player A has taken right. A has " + playerA + " golds.");
            }
            else
            {
                playerB += left > right ? pots.Left.Data : pots.Right.Data;
                if (left > right)
                    Console.WriteLine("Player B has taken left. B has " + playerB + " golds.");
                else Console.WriteLine("Player B has taken right. B has " + playerB + " golds.");
            }
            PrintPotsOfGoldGame(left > right ? pots.Left : pots.Right, playerA, playerB, !turn);
        }

        public double Optimize(Node<int> pots, int a = 0, int b = 0, double win = 0, bool turn = true)
        {
            if (turn) a += pots.Data;
            else b += pots.Data;
            if (pots.Left == null && pots.Right == null) return a > b ? 1 : 0;
            win += Optimize(pots.Left, a, b, win, !turn);
            win += Optimize(pots.Right, a, b, win, !turn);
            return win;
        }

    Sub Main()
        Dim pots As New List(Of Integer)
        pots.AddRange(Array.ConvertAll(Split(Console.ReadLine, " "), Function(s As String) CInt(s)).OrderBy(Function(p As Integer) p))

        Dim A As Integer, B As Integer
        Dim t As Boolean = False

        Dim potSelect As Action(Of Boolean) =
            Sub(isLeft As Boolean)
                    If isLeft Then
                        If t Then : B += pots.First : Else : A += pots.First : End If
                        pots.RemoveAt(0)
                    Else
                        If t Then : B += pots.Last : Else : A += pots.Last : End If
                        pots.RemoveAt(pots.Count - 1)
                    End If
            End Sub

        While pots.Count > 0
            If t Then
                If pots.Count >= 3 Then
                    Dim l1 As Integer = pots.First
                    Dim l2 As Integer = pots(1)
                    Dim r1 As Integer = pots.Last
                    Dim r2 As Integer = pots(pots.Count - 2)

                    If l1 > r1 Then
                        If l1 + r1 < l2 Then
                            potSelect(True)
                        Else
                            potSelect(False)
                        End If
                    Else
                        If l1 + r1 < r2 Then
                            potSelect(True)
                        Else
                            potSelect(False)
                        End If
                    End If
                Else
                    If pots.First > pots.Last Then
                        potSelect(True)
                    Else
                        potSelect(False)
                    End If
                End If
            Else
                If pots.First > pots.Last Then
                    potSelect(True)
                Else
                    potSelect(False)
                End If
            End If

            t = Not t
        End While

        Console.WriteLine("A: {0}, B: {1}", A, B)

        Console.ReadLine()
    End Sub

    static void exce25()
    {
        Scanner scan = new Scanner(System.in);
        String[] str = scan.nextLine().split(" ");
        int[] arr = new int[str.length];
        int a, b;
        int score = 0, n = 0;

        for (int i = 0; i < str.length; i++)
            arr[i] = Integer.parseInt(str[i]);

        a = 0;
        b = arr.length - 1;

        while (a != b)
        {
            if (b - a > 2)
            {
                int aa = arr[a] - Math.max(arr[a + 1], arr[b]);
                int bb = arr[b] - Math.max(arr[a], arr[b - 1]);

                if (aa > bb)
                {
                    if (n == 0)
                        score += arr[a];
                    a++;
                } else
                {
                    if (n == 0)
                        score += arr[b];
                    b--;

                }
            }
            else
            {
                if (arr[a] > arr[b])
                {
                    if (n == 0)
                        score += arr[a];
                    a++;
                } 
                else
                {
                    if (n == 0)
                        score += arr[b];
                    b--;
                }
            }
            n = (n+1)%2;
        }

        System.out.println(score);
    }

#!/usr/bin/env python
#-*- coding: utf-8 -*-

gold = [9,8,7,5,4,6,3,1,2]

def maximize(gold): #앞뒤 어느쪽을 선택할것인지 결정하는 함수
    if gold[0]+expect(gold[1:])> gold[-1]+expect(gold[:-1]):
        return 0 #앞
    else :
        return -1 #뒤
def expect(g): # 차례가 상대에게 넘어갔을 때 내가 가질 수 있는 기대값을 계산
    gold = g
    if len(gold)==2 : return min(gold)
    if len(gold)<=1 : return 0
    if maximize(gold) == 0:gold.pop(0) #상대가 하나를 선택해서 가져감
    else : gold.pop()
    if maximize(gold) ==0 : return gold[0]+expect(gold[1:])
    else : return gold[-1]+expect(gold[:-1])

A=B=0
while len(gold)>0:
    s = maximize(gold)
    print 'pots:',gold
    print 'A의 선택:',['앞','뒤'][s],
    A += gold.pop(s)
    print '  A점수: ',A
    print
    if len(gold)>0:
        s = maximize(gold)
        print 'pots:',gold
        print 'B의 선택:',['앞','뒤'][s],
        B += gold.pop(s)
        print '  B점수: ',B
        print
print 'A최종: ',A
print 'B최종: ',B

'''
출력예

pots: [9, 8, 7, 5, 4, 6, 3, 1, 2]
A의 선택: 앞   A점수:  9

pots: [8, 7, 5, 4, 6, 3, 1, 2]
B의 선택: 앞   B점수:  8

pots: [7, 5, 4, 6, 3, 1, 2]
A의 선택: 앞   A점수:  16

pots: [5, 4, 6, 3, 1, 2]
B의 선택: 앞   B점수:  13

pots: [4, 6, 3, 1, 2]
A의 선택: 뒤   A점수:  18

pots: [4, 6, 3, 1]
B의 선택: 뒤   B점수:  14

pots: [4, 6, 3]
A의 선택: 뒤   A점수:  21

pots: [4, 6]
B의 선택: 뒤   B점수:  20

pots: [4]
A의 선택: 뒤   A점수:  25

A최종:  25
B최종:  20
'''

파이썬3.4입니다. 역시 재귀함수;;;로 풀었는데요. 최적값 하나만 나오는게 아니라, 몇개의 경우의수를 출력합니다.
의도한것은 아니고 최적의 값 하나를 출력하는것을 잘 못하겠네요...;;;
굉장히 너저분 하고 부족하지만, 일단 비슷한 결과가 나와 올려봅니다.

def f(pots, a = 0, b = 0, howa = '', howb = ''):
    if not pots:
        print(a, b, abs(a - b), howa, howb) if a > b else None #a점수, b점수, 점수차이, a의 선택, b의 선택 순으로 출력
        return
    else:
        if len(pots) >= 2:
            if sum(pots[2:]) < sum(pots[1:-1]): #a가 왼쪽을 선택할때 나머지의 합이 작은쪽으로 b가 선택
                f(pots[2:], a + pots[0], b + pots[1], howa + ' ' + str(pots[0]), howb + ' ' + str(pots[1]))
            else:
                f(pots[1:-1], a + pots[0], b + pots[-1], howa + ' ' + str(pots[0]), howb + ' ' + str(pots[-1]))
            if sum(pots[:-2]) < sum(pots[1:-1]): #a가 오른쪽을 선택할때 나머지의 합이 작은쪽으로 b가 선택
                f(pots[:-2], a + pots[-1], b + pots[-2], howa + ' ' + str(pots[-1]), howb + ' ' +str(pots[-2]))
            else:
                f(pots[1:-1], a + pots[-1], b + po감ts[0], howa + ' ' + str(pots[-1]), howb + ' ' + str(pots[0]))
        elif len(pots) == 1: #하나가 남을경우 a가 가져감
            f(None, a + pots[0], b, howa + ' ' + str(pots[0]), howb)

pots = [9, 8, 7, 5, 4, 6, 3, 1, 2]
f(pots)

Ruby

sum = ->p { [*p][0]? [ p[0] + [sum[p[1..-2]], sum[p[2..-1]]].min,
                      p[-1] + [sum[p[1..-2]], sum[p[0..-3]]].min ].max : 0 }

Test

expect(sum[[9,8,7,5,4,6,3,1,2]]).to eq 25
expect(sum[[3,6,2,8,1,9,4,5,7]]).to eq 17 #=> B가 이길수 밖에 없는 상황.

남아있는 금화 리스트를 인자로 받은 후에 (내가 얻을 최적 금화, 그에 따라 상대방이 얻을 최적 금화)를 리턴하는 함수를 작성했습니다.

왼쪽을 선택했을 때의 나머지와 오른쪽을 선택했을 때의 나머지를 가지고 재귀적으로 호출하면 각각

• (왼쪽을 선택했을 때 상대방의 최대금액, 내가 더 얻을 금액)
• (오른쪽을 선택했을 때 상대방의 최대금액, 내가 더 얻을 금액)

을 얻을 수 있고, 그 중에 내가 더 얻을 금액에 현재 찬스에서 선택한 왼쪽/오른쪽 항아리 금액을 더했을 때 큰 것을 취합니다.

처음에는 최종 금액만 계산하게 했는데, 선택한 금화 리스트를 출력하게 해서 어떤 식으로 선택했는지 알아볼 수 있게 수정했습니다.

def do(xs):
    left, *tail, right = xs
    if len(tail) is 0:
        return ([left], [right]) if left > right else ([right], [left])
    # 왼쪽을 선택할 경우
    p, q = do(tail + [right])
    r1 = [left]+q
    # 오른쪽을 선택할 경우
    s, t = do([left] + tail)
    r2 = [right]+t
    if r1 > r2:
        return r1, p
    return r2, s

print(do([3,4,9,7]))
# ([3, 9], [7, 4])

2^n이 1 ~ 2^n-1의 합보다 크다는 사실에서 착안하여 A는 남은 수가 비슷할때는 별 전략없이 큰 수를 택하다가 판별을 뒤집을 수 있는 큰 수가 나왔을 때는 B가 가져가지 못하게 알고리즘을 짜는거죠 (각 시행마다 시뮬레이션을 돌리는 것이죠. 자료구조에 보면 최악의 경우를 따질 때 반 반 나눠서 계산하는 거 있잖아요? 그걸 적용시키면 될 것 같아요) 그럼 반대쪽이 계속 줄어들다가 A가 그 금화를 가져가는 거죠

Delphi 2010 상파님 코드 사용 (4, 6, 1, 1, 2 경우 Fail Bug Fix(2) - 결과 동율)

function fnBest_GoldPos(const gold: array of Integer; Lines: TStrings): Integer;

  function maximize(L, R: Integer): Integer; // 앞뒤 어느쪽을 선택할것인지 결정하는 함수 
  var
    c1, c2: Integer;
    function expect(L, R: Integer): Integer; // # 차례가 상대에게 넘어갔을 때 내가 가질 수 있는 기대값을 계산 
    var
      nLen: Integer;
    begin
      nLen := R - L + 1;
      if nLen = 2 then
        exit(Min(gold[L], gold[R]));
      if nLen = 1 then // Bug Fix 
        exit(gold[L]);
      if nLen <= 0 then
        exit(0);

      if maximize(L, R) = 0 then
        Inc(L) // #상대가 하나를 선택해서 가져감 
      else
        dec(R); // 

      if maximize(L, R) = 0 then
      begin
        result := gold[L] + expect(L + 1, R);
      end
      else
      begin
        result := gold[R] + expect(L, R - 1);
      end;
    end;

  begin
    c1 := gold[L] + expect(L + 1, R);
    c2 := gold[R] + expect(L, R - 1);

    if c1 = c2 then // Bug Fix 
    begin
      // 같은 값이면 큰쪽으로? 
      c1 := gold[L];
      c2 := gold[R];
    end;

    if c1 > c2 then
      exit(0) // #앞 
    else
      exit(-1); // #뒤 
  end;

  function IntArrayToStr(a: array of Integer; L, R: Integer): string;
  var
    i: Integer;
  begin
    result := '';
    for i := L to R do
      if i = L then
        result := IntToStr(a[i])
      else
        result := result + ', ' + IntToStr(a[i])
  end;

var
  a, b, L, R, s: Integer;
  txt: string;
  bA: boolean;
begin
  a := 0;
  b := 0;
  L := 0;
  R := High(gold);
  bA := true;
  while R - L >= 0 do
  begin
    Lines.Add('Pot: ' + IntArrayToStr(gold, L, R));

    s := maximize(L, R);
    if s = 0 then
    begin
      s := gold[L];
      txt := '앞 ' + IntToStr(s);
      Inc(L);
    end
    else
    begin
      s := gold[R];
      txt := '뒤 ' + IntToStr(s);
      dec(R);
    end;
    if bA then
    begin
      Lines.Add('A의 선택: ' + txt);
      Inc(a, s);
      Lines.Add('A의 점수: ' + IntToStr(a));
    end
    else
    begin
      Lines.Add('B의 선택: ' + txt);
      Inc(b, s);
      Lines.Add('B의 점수: ' + IntToStr(b));
      Lines.Add('');
    end;
    bA := not bA;
  end;
  if a = b then
    txt := '동율'
  else if a > b then
    txt := '승'
  else
    txt := '패';

  Lines.Add(format('## 결과  A의 점수: %d, B의 점수: %d  %s', [a, b, txt]));
  Lines.Add('');
  result := a;
end;

procedure TForm4.btnPotsofgoldgameClick(Sender: TObject);
begin
  Memo1.Lines.Clear;
  fnBest_GoldPos([9, 8, 7, 5, 4, 6, 3, 1, 2], Memo1.Lines);
  fnBest_GoldPos([4, 6, 3, 1, 1], Memo1.Lines);
  fnBest_GoldPos([4, 6, 1, 1, 2], Memo1.Lines);
end;

#include <stdio.h>
#include <stdlib.h>

int* pot;
int selectPot(bool b, int head, int rear,int A, int div);
void main() {
    int size;
    printf("항아리의 갯수는?\n");
    scanf("%d" , &size);

    pot = (int*) malloc (sizeof(int) * size);
    printf("항아리당 금화 입력\n");
    for(int i=0; i< size ;i++) {
        scanf("%d" , &pot[i]);
    }


    int A1, A2, head, rear;
    int B1, B2;
    head = 0;
    rear = size-1;
    for(int i=0; i<= size/2 ;i++) {
        A1 = selectPot(true,head,rear,0,0);
        A2 = selectPot(false,head,rear,0,0);
        if(A1 > A2) {
            printf("A는 %d를 선택 \n", pot[head]);
            head++;
        }
        else {
            printf("A는 %d를 선택 \n", pot[rear]);
            rear--;
        }

        B1 = selectPot(true,head,rear,0,0);
        B2 = selectPot(false,head,rear,0,0);
        if(B1 > B2) {   
            head++;
        }
        else {
            rear--;
        }
    }
}
int selectPot(bool b, int head, int rear,int A, int div) {
    if(b == true) {
        if(div%2==0)
            A = A + pot[head];
        head++;
    }
    else {
        if(div%2==0)
            A = A + pot[rear];
        rear--;
    }
    div++;

    if(head >= rear) {
        return A;
    } else {
        selectPot(true,head,rear, A, div);
        selectPot(false,head,rear, A, div);
    }
}

a=[]
b=[]
def find_max(fmax):
    if len(fmax)<=1:
        return 0
    m=0
    n=0
    if fmax[0]>fmax[-1]:
        m=fmax[0]
        n=fmax[-1]
    elif fmax[0]<fmax[-1]:
        m=fmax[-1]
        n=fmax[0]
    a.append(m)
    b.append(n)
    del fmax[0]
    del fmax[-1]
    print("a:",a)
    print("b:",b)
    find_max(fmax)
arr=[7,2,1,3,4,5]
find_max(arr)

Python3

풀이들을 보고 문제를 겨우 이해했네요.

def maximize(pots):
    if len(pots) < 2:
        return sum(pots)

    left = pots[0] + ( sum(pots[1:]) - maximize(pots[1:]) )
    right = pots[-1] + ( sum(pots[:-1]) - maximize(pots[:-1]) )

    return max([left, right])

어떤 플레이어 X가 pots[0]을 뽑은 경우,

남은 pots[1:]에서 상대가 최적의 선택들을 하고 그 합을 리턴합니다: maximize(pots[1:])

sum(pots[1:])에서 이 리턴값을 빼면 남은 pots[1:]에서 플레이어 X가 가질 수 있는 금이 됩니다.

X가 pots[-1]을 뽑는 경우도 마찬가지이고, 두 경우 중 X가 가질 수 있는 금이 큰 쪽을 선택합니다.

.

그리고 중복이 많을 거 같아서 DP로 바꿔봤습니다.

남아있는 pots를 key, 리턴값을 value로 사전을 만듭니다.

리스트는 키로 해싱이 안된다 하니 리스트 대신 튜플을 사용해야 합니다.

dic = dict()

def maximize(pots):
    global dic

    if pots in dic:
        return dic[pots]

    if len(pots) < 2:
        dic[pots] = sum(pots)
        return sum(pots)

    left = pots[0] + ( sum(pots[1:]) - maximize(pots[1:]) )
    right = pots[-1] + ( sum(pots[:-1]) - maximize(pots[:-1]) )
    best = max([left, right])

    dic[pots] = best
    return best

1. 파이썬 3.6입니다
2. 값이 양수가 나오면 A가 이긴것이고 음수가 나오면 B가 이긴겁니다.
3. 누가 뭘 취했는지는 나중에 짜보겠습니다

def score(gold):
    result = []
    if len(gold)==1:
        return gold[0]
    elif len(gold)==2:
        return abs(gold[0]-gold[1])
    elif len(gold)>=3:
        return max(gold[0]-score(gold[1:]),gold[-1]-score(gold[:-1]))
    else:
        return '항아리가 없다'

1. sequence함수로 원하는 결과를 얻고, 그 결과는 골드량 합산이 아니라 가져가는 순서입니다.
2. sequence함수에서 A와 B가 가져간 골드량을 계산하게 만들 수 있습니다.

def chosen_index(gold):
    if gold[0]-score(gold[1:])>=gold[-1]-score(gold[:-1]):
        return 0
    else:
        return -1 

def score(gold): #여기가 중요한 파트인데, 게임을 이기기 위한 A와 B의 골드량차이만을 중점으로 생각한 함수입니다.
    if len(gold)==1:
        return gold[0]
    elif len(gold)==2:
        return abs(gold[0]-gold[1])
    elif len(gold)>=3:
        return max(gold[0]-score(gold[1:]),gold[-1]-score(gold[:-1]))
    else:
        return 0

def sequence(gold):
    result=[[],[]]
    while len(gold)>0:
        result[0].append(chosen_index(gold))
        result[1].append(gold[chosen_index(gold)])
        gold.pop(chosen_index(gold))
    return print('가져가지는 항아리 순서:{}, 가져가지는 골드량:{}'.format(result[0],result[1]))

[Python 3.6]

def maximizeGold(pots):
    if not pots: return 0
    if len(pots) == 1: return pots[0]
    if len(pots) == 2: return max(pots[0], pots[1])
    return max(pots[0] + min(maximizeGold(pots[2:]), maximizeGold(pots[1:-1])), pots[-1] + min(maximizeGold(pots[1:-1]), maximizeGold(pots[0:-2])))

pots = [4, 5, 6, 1, 2, 3, 11, 6, 2, 5, 11, 2, 10]
print(maximizeGold(pots))

def plan1(a):
    if len(a) == 2:
        return max(a)
    elif len(a) == 1:
        return a[0]
    else:
        def plan2(a):
            return min((plan1(a[1:]), plan1(a[:len(a) - 1])))
        return max(a[0]+plan2(a[1:]), a[len(a)-1]+plan2(a[:len(a)-1]))


l = list(map(int, input("항아리에 들어있는 금의 양을 입력하시오 (공백으로 구분):").split(' ')))
print(plan1(l))
result = list()
while len(l) >= 3:
    if l[0]+min(plan1(l[1:len(l)-1]),plan1(l[2:])) > l[len(l)-1]+min(plan1(l[1:len(l)-1]),plan1(l[:len(l)-2])):
        result.append(l[0])
        if plan1(l[1:len(l)-1]) > plan1(l[2:]):
            l = l[2:]
        else:
            l = l[1:len(l)-1]

    else:
        result.append(l[len(l)-1])
        if plan1(l[1:len(l)-1]) > plan1(l[:len(l)-2]):
            l = l[:len(l)-2]
        else:
            l = l[1:len(l)-1]
result.append(max(l))
print(result)

#include<iostream>
#include"stdafx.h"

void input_gold_coin(deque<int> &pot)
{
    srand((unsigned int)time(NULL));
    for (vector<int>::size_type i = 0; i < pot.size(); i++)
    {
        pot[i] = rand() % 200;
    }
}
void Judge(deque<int>&pot, int &score)
{
    int select_num, compare_num, a, b;
    if (pot.size() > 2)
    {
        select_num = pot[0];
        if (pot[1] > pot[pot.size() - 1]) compare_num = pot[1];
        else compare_num = pot[pot.size() - 1];
        a = select_num - compare_num;
        select_num = pot[pot.size() - 1];
        if (pot[0] > pot[pot.size() - 2]) compare_num = pot[0];
        else compare_num = pot[pot.size() - 2];
        b = select_num - compare_num;
        if (a > b)score += pot[0], pot.pop_front();
        else score += pot[pot.size() - 1], pot.pop_back();
    }
    else
    {
        if (pot.size() == 1)score += pot[0];
        else
        {
            if (pot[0] > pot[1]) score += pot[0], pot.pop_front();
            else score += pot[1], pot.pop_back();
        }
    }
}

int main()
{
    srand((unsigned int)time(NULL));
    bool turn_a = true;
    int num_of_pot = 4 + rand() % 100;
    int score_a = 0, score_b = 0;
    deque<int> pot(num_of_pot);
    input_gold_coin(pot);
    int i = pot.size();
    while (i>0)
    {
        for (int i = 0; i < pot.size(); i++)
            cout << pot[i] << " ";
        cout << endl;
        cout << "Score_A:" << score_a << endl;
        cout << "Score_B:" << score_b << endl;
        if (turn_a) Judge(pot, score_a), turn_a = false;
        else Judge(pot, score_b), turn_a = true;
        i--;
    }
}

점점 개선해 나가야겠네요..

package com.code.dojang.etc;

import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.LinkedBlockingDeque;

public class Question21 {

    /**
     * 
     *A, B 두명의 플레이어가 있다.

        한개의 선 위에 여러개의 금 항아리가 놓여져 있다. 각 항아리는 금화를 담고 있다. (플레이어는 각 항아리에 얼마의 금화가 들어있는지 알 수 있다.) 각 플레이어는 교대로 선에 놓여있는 양쪽 가장자리 항아리 중에서 한 개씩 선택 할 수 있다. (가장 우측 항아리 또는 가장 좌측 항아리 중 하나를 선택해야 한다.)

        모든 항아리 선택이 끝난 후 가장 많은 금화를 차지한 플레이어가 승리하게 된다.

        이 게임의 목표는 A가 먼저 게임을 시작할 때 A가 가장 많은(Maximize) 금화를 가질 수 있도록 하는 것이다. B 역시 최적의 알고리즘으로 항아리를 선택한다고 가정한다.

        A가 이길 수 있는 최선의 전략을 찾아 보시오.

        그리고 이것을 프로그래밍 코드로 작성 해 보시오. 
     *
     */
    public static double log2(double x) {
        return Math.log(x) / Math.log(2);
     }

    public static void main(String[] args) {
        Versus2 v = new Versus2();

        Player2 A = new Player2(v);
        Player2 B = new Player2(v);
        int playCount = 10000;
        for(int i = 0; i < playCount ; i++) {
            while(true) {
                try {
                    A.run();
                    B.run();
                }catch(NullPointerException e) {
                    System.out.println(A.getCoinCount());
                    System.out.println(B.getCoinCount());
                    if(A.getCoinCount() > B.getCoinCount()) {
                        A.setWins(1);
                    }else if (A.getCoinCount() < B.getCoinCount()) {
                        B.setWins(1);
                    }
                    v = new Versus2();
                    A.init(v);
                    B.init(v);
                    break;
                }
            }
        }
        double winRating = (float)A.getWins()/(float)playCount *100;
        System.out.println(A.getWins()+" : "+B.getWins());
        System.out.println("A 의 승률 : "+ winRating +"%");

    }



}

class Pot2{
    private int goldCoin = 0;

    public int getGoldCoin() {
        return goldCoin;
    }

    Pot2(){
        this.goldCoin = new Random().nextInt(10000000);
    }
}

class Player2{
    int coinCount = 0;
    int wins = 0;
    Versus2 cls;

    Player2(Versus2 q){
        this.cls = q;
    }

    public int getWins() {
        return wins;
    }

    public void setWins(int wins) {
        this.wins += wins;
    }

    public int getCoinCount() {
        return coinCount;
    }

    public void init(Versus2 v) {
        this.cls = v;
        coinCount = 0;
    }

    public void setCoinCount(int coinCount) {
        this.coinCount += coinCount;
    }

    public int calCost(String path, Deque line) {//path는 나와 상대 차례를 순서대로 가리키는 0또는 1의 연속적인 스트링. 1은 왼쪽, 0은 오른쪽 항아리를 Get 
        Deque<Pot2> tmpLine = new LinkedBlockingDeque<Pot2>();
        tmpLine.addAll(line);
        int mySum = 0;
        int otherSum = 0;
        for(int i = 0; i < tmpLine.size(); i ++) {
            if(i%2 == 1) {//상대차례일때
                if(path.charAt(i) =='1') {
                    otherSum += tmpLine.pollFirst().getGoldCoin();                  
                }else if (path.charAt(i) =='0') {
                    otherSum += tmpLine.pollLast().getGoldCoin();                   
                }
            }else {//내 차례일때
                if(path.charAt(i) =='1') {
                    mySum += tmpLine.pollFirst().getGoldCoin();                 
                }else if (path.charAt(i) =='0') {
                    mySum += tmpLine.pollLast().getGoldCoin();                  
                }
            }
        }
        return mySum;       
    }

    public int thinking(Deque line) {//모든 경우의수 계산 후  가장 많은 코스트 선택지 선택
        StringBuffer path = new StringBuffer();
        Map<String, Integer> costs = new HashMap<>();//<pathString, totalCost>
        for(int i = 1 ; i < (int)Math.pow(2, line.size()+1); i++) {// 모든 경우의 수 path 출력
            StringBuffer path2 = new StringBuffer();
            for(int p = 0 ; p <(int)Question21.log2((int)Math.pow(2, line.size())) - (int)Question21.log2(i); p++) {
                path2.append("0");
            }
            path2.append(Integer.toBinaryString(i));
            costs.put(path2.toString(), calCost(path2.toString(),line));
        }

        for(String key : costs.keySet()) {
            Integer val = costs.get(key);
        }

        List<Map.Entry<String, Integer>> maxs = new ArrayList<Map.Entry<String, Integer>>();
        Map.Entry<String, Integer> maxEntry = null;
        for (Map.Entry<String, Integer> entry : costs.entrySet()) {

            if (maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0) {
                maxs = new ArrayList<Map.Entry<String, Integer>>();
                maxEntry = entry;
                //compareTo를 이용해 제일 높은 map값이 maxEntry에 저장됨
            }else if (maxEntry.getValue().compareTo(entry.getValue())==0) {
                maxs.add(entry);
            }
        }
        int matched0 = 0;
        int matched1 = 0;
        for(Map.Entry<String, Integer> e : maxs) {
            if(e.getKey().charAt(0) =='0') {
                matched0++;
            }else {
                matched1++;
            }
        }
        if(matched0 > matched1) {
            return 0;
        }else {
            return 1;
        }

         //0은 오른쪽꺼 빼기, 1은 왼쪽꺼 빼기
    }

    public void run() {
        int determine = 0;
        determine = thinking(cls.line);
        this.setCoinCount(cls.getPot2Coin(determine).getGoldCoin());
    }
}

class Versus2{
    Deque<Pot2> line;
    int potCount = 8;
    Versus2(){

        line = new LinkedBlockingDeque();

        for(int i = 0; i  < potCount; i++) {
            line.add(new Pot2());           
        }
        printCurrLine();
    }
    public synchronized Pot2 getPot2Coin(int direction) {
        if(direction >0) {
            return (Pot2) line.pollFirst();
        }else {
            return (Pot2) line.pollLast();          
        }
    }

    public void printCurrLine() {
        for(Pot2 p : line) {
            System.out.print("-"+p.getGoldCoin()+"-");
        }
        System.out.println();
    }


}

A의 승률이 80%정도 나오네요.. 무조건 이겨야 하는건가요..? 무식한 탓에 Brute Force식으로 했습니다 ㅠㅠㅠ

파이썬 3;

아래 출처의 모범 답안을 파이썬으로 변경하였습니다. https://www.careercup.com/question?id=15422849 역시 고수들은 뭔가 다르네요.

def max_coin(coin, start, end):
    if start > end:
        return 0
    a = coin[start] + min(max_coin(coin, start + 2, end), max_coin(coin, start + 1, end - 1))
    b = coin[end] + min(max_coin(coin, start + 1, end - 1), max_coin(coin, start, end - 2))
    return max(a, b)


list3 = [1, 4, 10, 8, 100, 2, 25]
print(max_coin(list3, 0, 6))

from random import randint

memo = {}
def pot(v):
  if len(v) == 1: return v, []
  if len(v) == 2: return [max(v)], [v.index(max(v))]

  l_pop = memo.get(tuple(v[1:]), pot(v[1:]))
  r_pop = memo.get(tuple(v[:-1]), pot(v[:-1]))
  if sum(l_pop[0]) < sum(r_pop[0]):
    memo[tuple(v)] = (v[:1]+( pot(v[1:-1])[0] if l_pop[1][0] else pot(v[2:])[0] ), \
                    [0]+( pot(v[1:-1])[1] if l_pop[1][0] else pot(v[2:])[1] ))
  else:
    memo[tuple(v)] = (v[-1:]+( pot(v[:-2])[0] if r_pop[1][0] else pot(v[1:-1])[0] ), \
                    [1]+( pot(v[:-2])[1] if r_pop[1][0] else pot(v[1:-1])[1] ))
  return memo[tuple(v)]

for __ in range(10):
  test = [randint(1,100) for _ in range(10)]
  Apot = pot(test)[0]
  Bpot = test[:]
  for i in Apot: Bpot.remove(i)
  print(test, '\n', sum(Apot), ':', sum(Bpot))

[60, 98, 85, 19, 62, 13, 10, 51, 23, 62]
 255 : 228
[1, 28, 58, 99, 19, 94, 37, 34, 75, 17]
 272 : 190
[29, 89, 86, 83, 8, 37, 5, 50, 38, 83]
 342 : 166
[59, 88, 75, 4, 54, 53, 77, 76, 54, 73]
 338 : 275
[93, 6, 62, 40, 45, 46, 59, 61, 37, 6]
 296 : 159
[92, 97, 48, 79, 99, 92, 71, 57, 42, 26]
 352 : 351
[21, 59, 91, 47, 87, 47, 43, 16, 13, 33]
 267 : 190
[58, 67, 63, 32, 39, 81, 34, 17, 57, 60]
 279 : 229
[33, 22, 29, 43, 78, 98, 9, 95, 85, 94]
 352 : 234
[31, 67, 97, 30, 30, 88, 91, 65, 32, 22]
 281 : 272

def pot(a):
    if not a:
        return 0
    a_left_val  = a[0]  + min(pot(a[2:]), pot(a[1:-1]))
    a_right_val = a[-1] + min(pot(a[1:-1]), pot(a[:-2]))
    return max(a_left_val, a_right_val)

test_set = [[9, 8, 7, 5, 4, 6, 3, 1, 2], [1,3,4,5,1]]
for a in test_set: 
    print(pot(a))

python3.7
지적있으시면 댓글 부탁드립니다.

'''
처음에 몇 번까지의 이후의 수를 계산해야하는지 고민했었습니다. 생각을 해보니, 바로 다음 번 선택까지만 계산을 하면 결과에 영향을 미치지 않는다는 것을 알게되었습니다.

또한 B 역시도 최적의 선택을 한다고 하여, 같은 알고리즘으로 항아리를 선택하도록 짜보았습니다.
'''

import numpy as np
import copy

pots_num = np.random.randint(1, 10)
pots = list(np.random.randint(1, 100, pots_num))
archive = copy.deepcopy(pots)

prob = [100*i/sum([i for i in pots if i>=np.mean(pots)]) if i>= np.mean(pots) else -100*i/sum([i for i in pots if i<np.mean(pots)]) for i in pots] # 각 요소 선택에 대한 승리 패배 확률(prob.)

# 각각의 합계 집합
a = list()
b = list()

# 무조건 상대가 다음번에 고를 경우의 수와의 득실만 계산하고, 같을 경우 다음 경우의 수로 재귀호출한다.
def compute(lst, n, m):
    if len(lst)==1:
        return 0
    get_first = lst[n] - (lst[n+1] if lst[n+1] > lst[m] else lst[m])
    get_last = lst[m] - (lst[m-1] if lst[m-1] > lst[n] else lst[n])
    return compute(lst, n+1, m-1) if get_first==get_last else 0 if get_first>get_last else -1

# 반복 수행
while True:
    if len(pots)==0:
        break
    else:
        a.append(pots[compute(prob,0,-1)])
        del pots[compute(prob,0,-1)]

    if len(pots)==0:
        break
    else:
        b.append(pots[compute(prob,0,-1)])
        del pots[compute(prob,0,-1)]

print("\n최초의 항아리는 {}였습니다.\nA의 총 합계는 {}\nB의 총 합계는 {}\n결과 : {}".format(archive, sum(a), sum(b), 'A 승리' if sum(a)>sum(b) else 'B 승리' if sum(a)<sum(b) else '무승부'))

재귀함수를 사용함

def P(m, n, L):  #재귀함수. 각 구간에서 얻을수있는 최대값과 최선의 선택지를 반환.
    if m == 0:
        C = L[n:n+3]
        first_pick = max(C[0], C[2])
        pick = C.index(first_pick)
        C.remove(first_pick)
        return [first_pick + min(C), 1 if pick==0 else 0]

    a = sum(L[n:n+m+3]) - P(m-1, n+1, L)[0]
    b = sum(L[n:n+m+3]) - P(m-1, n, L)[0]
    if a > b: return [a, 1]
    else : return [b, 0]

def FindSolution(L):  #각자의 최선의 선택지를 나열해주는 함수
    m = len(L) - 3
    n = 0
    T = []
    while m >= 0:
        r = P(m, n, L)[1]
        T.append(r)
        m -= 1
        n += r

    return list(map(lambda x : 'left' if x==1 else 'right', T))  #1은 왼쪽픽을, 0은 오른쪽픽을 뜻함.



L = [3, 100, 1000, 500, 4, 20]
print("A와 B가 얻을수 있는 금화는 ", P(len(L)-3, 0, L)[0], " : ", sum(L)-P(len(L)-3, 0, L)[0])
print("각자의 최선의 선택지는 ", FindSolution(L))

def solution(lst):

    n = sum(lst)

    if len(lst)<=2:
        return max(lst)



    return max(n-solution(lst[1:]), n-solution(lst[:-1]))

def printing(lst):
    sgn = 0
    while len(lst)>=2:
        sgn +=1
        n = sum(lst)
        a = n-solution(lst[1:])
        b = n-solution(lst[:-1])

        if a>=b:
            if sgn%2==1:               
                print(lst,"에서 A가",lst[0],'을 꺼낸다')
            else:
                print(lst,"에서 B가",lst[0],'을 꺼낸다')
            lst.pop(0)
        elif a<b:
            if sgn%2==1:               
                print(lst,"에서 A가",lst[-1],'을 꺼낸다')
            else:
                print(lst,"에서 B가",lst[-1],'을 꺼낸다')

            lst.pop(-1)

s = []
for i in range(10):
    s.append(random.randint(1,10))
print(s)
print(solution(s))
printing(s)

#(내가 고른 선택지 - 상대방이 고를수 있는 선택지)가 가장 작은 값을 선택하는 함수 생성
def Best_choice(choice1,choice2,next1,next2):
    if min(choice1-next1, choice1-choice2)>min(choice2-next2, choice2-choice1):
        return 0
    else:
        return -1

import random

#A가 먼저 시작해도 B가 이긴 횟수를 세기위해 10000번 반복 시행
cnt = 0 
for i in range(0,10000):
    #1~100개 금화가 들어있는 항아리 10개 생성
    gold_pots = []
    for i in range(0,10):
        gold_pots.append(random.randint(0,100))
    Aplayer = []
    Bplayer = []

    while gold_pots:
        index = Best_choice(gold_pots[0],gold_pots[-1],gold_pots[1],gold_pots[-2])
        Aplayer.append(gold_pots.pop(index))
        Bplayer.append(gold_pots.pop(index))
    if sum(Aplayer)<sum(Bplayer):
        cnt += 1

print(cnt)

다른 분들의 답이 A가 이기는 확률이 80%정도 되길래 더 높일 수 있는 방법이 없을까 생각하다가 다른 알고리즘의 함수를 만들어 봤습니다. 10000번 시행 결과 90%정도는 A가 이깁니다.

Fortran 77

포트란 77 코드 필요하신 분이 없겠지만 일단 이런 식으로 하면 됩니다. 승률은 경우에 따라서 다른데 항아리 10개(금화 랜덤) 기준으로 84~87% 정도입니다.

c234567
      program gold_pot
      integer a(1:100), n, aget, bget, i, awin, bwin, j
      real r(1:10)

      open(900, file='result.dat')

      awin=0
      bwin=0

      do j=1,1000

      n=10

      call RANDOM_NUMBER(r)

      do i=1,10
          a(i)=int(10*r(i))
      end do


c a와 b가 가진 금화를 0으로 초기화
      aget=0
      bget=0

      do i=1,n
          print *, a(i)
      end do

   10 continue

          If (n. EQ. 0) then
              goto 20
          end if

      call strat(n, a, aget)

          If (n. EQ. 0) then
              goto 20
          end if

      call strat(n, a, bget)

      goto 10

  20  continue    


      if (aget .GT. bget) then
          awin=awin+1
          write (900,*) aget, bget, 'A won'
      else if (bget .GT. aget) then
          bwin=bwin+1
          write (900,*) aget, bget, 'B won'
      else
          write (900,*) aget, bget, 'Draw'
      end if

      end do

      print *, 'A의 승률', real(awin)/1000.
      print *, 'B의 승률', real(bwin)/1000.

      stop
      end


c 전략 서브루틴
      subroutine strat(n, a, get)
      integer a(1:n), b1, bn, n, get, i, m1, mn, c1, cn

c 1번(왼쪽) 선택시 최소이익
      m1=min(a(1)-a(2), a(1)-a(n))
      If (m1 .EQ. (a(1)-a(2))) then
          b1 = a(1)-a(2)
      Else
        b1 = a(1)-a(n)
      End if
c n번(오른쪽) 선택시 최소이익
      mn=min(A(n)-A(1), A(n)-A(n-1))
      If (mn .EQ. A(n)-A(1)) then
          bn = A(n)-A(1)
      else
        bn = A(n)-A(n-1)
      end if

c 왼쪽과 오른쪽의 경우를 생각해서 최소이익이 큰 쪽을 선택
c 선택 후 get에 더함
c 왼쪽 선택, n번의 데이터를 n-1번에 덮어씌움
      If (b1 .GE. bn) then
          get=get+a(1)
        do i=1,n-1
            a(i) = a(i+1)
          end do
c 오른쪽 선택, n번의 데이터를 지움
      else
          get=get+a(n)
        A(n) = 0
      end if
      n=n-1

      return
      end

파이썬으로 작성했습니다.

def the_game(pot_num):
#게임 준비

    game_line = []
    import random
    def new_game_line(n):
        while len(game_line) < n:
            game_line.append(int(random.randrange(1,100)))
        return game_line
    game_line = new_game_line(pot_num)
    start_game_line = game_line[:]
#게임 시작
    big_one = 0
    small_one = 0
    new_one = 0

    def set_b_s_n():
        if game_line[0] > game_line[-1]:
            big_one = game_line[0]
            small_one = game_line[-1]
            new_one = game_line[1]
            return big_one, small_one, new_one
        elif game_line[0] < game_line[-1]:
            big_one = game_line[-1]
            small_one = game_line[-1]
            new_one = game_line[-2]
            return big_one, small_one, new_one

    def choice():
            if new_one < big_one: #큰거 뽑기
                return big_one
            elif new_one > big_one: #작은거 뽑기
                return small_one

    class setting():
        def __init__(self):
            self.loss = 0
            self.new_loss = 0
            self.list = []
        def choose(self):
            if choice() == big_one:
                if self == A:
                    A.list.append(choice())
                elif self == B:
                    B.list.append(choice())
                game_line.remove(choice())
            elif choice() == small_one:
                self.loss += (big_one - small_one)
                self.new_loss += (new_one - big_one)
                if self.loss > self.new_loss:
                    if self == A:
                        A.list.append(big_one)
                    elif self == B:
                        B.list.append(big_one)
                    game_line.remove(big_one)
                    self.loss = 0
                    self.new_loss = 0
                elif self.loss <= self.new_loss:
                    if self == A:
                        A.list.append(choice())
                    elif self == B:
                        B.list.append(choice())
                    game_line.remove(choice())

    A = setting()
    B = setting()

#A의 차례
    while len(game_line) > 2:

        big_one, small_one, new_one = set_b_s_n()
        A.choose()
        if len(game_line) == 2:
            if game_line[0] > game_line[1]:
                B.list.append(game_line[0])
                A.list.append(game_line[1])
            elif game_line[0] < game_line[1]:
                B.list.append(game_line[1])
                A.list.append(game_line[0])
            break
#B의 차례
        big_one, small_one, new_one = set_b_s_n()
        B.choose()
        if len(game_line) == 2:
            if game_line[0] > game_line[1]:
                A.list.append(game_line[0])
                B.list.append(game_line[1])
            elif game_line[0] < game_line[1]:
                A.list.append(game_line[1])
                B.list.append(game_line[0])
            break

    print('game line:', start_game_line)
    print("A's gold:", A.list, "\n\ttotal: ", sum(A.list))
    print("B's gold:", B.list, '\n\ttotal: ', sum(B.list))
    if sum(A.list) > sum(B.list):
        print("winner is: A")
    elif sum(A.list) < sum(B.list):
        print("winner is: B")
    else:
        print("DRAW")

N이 들어있는 금화수 배열이라면 A가 가질 수 있는 최대 금화는 bestChoice(N)의 첫번째 값.

def bestChoice(N):
    if len(N) == 1:
        return N[0], 0

    r1 = bestChoice(N[1:])
    r2 = bestChoice(N[:-1])
    return max(r1[1] + N[0], r2[1] + N[-1]), min(r1[0], r2[0])

#hang=[9,8,7,5,4,6,3,1,2]

k=1
a=[]
b=[]

def choose(hang):
    while k<len(hang):
        if hang[0] > hang[len(hang)-k]:
            a.append(hang[0])
            hang=hang[1:]
        else:
            a.append(hang[len(hang)-k])
            hang=hang[:-1]
        if hang[0] > hang[len(hang)-k]:
            b.append(hang[0])
            hang=hang[1:]
        else:
            b.append(hang[len(hang)-k])
            hang=hang[:-1]
    a.append(hang[0])
choose(hang)

print('A:',a, 'Total:',sum(a))
print('B:',b, 'Total:',sum(b))

def game(A, B, pots):
    if len(pots)==3:
        A.append(max(pots[0], pots[-1]))
        A.append(min(pots))
        return

    a = pots[0] - max(pots[1], pots[-1])
    b = pots[-1] - max(pots[0], pots[-2])
    if a > b:
        if len(A) >= len(B):
            B.append(pots[0])
        else:
            A.append(pots[0])
        game(A, B, pots[1:])
    else:
        if len(A) >= len(B):
            B.append(pots[-1])
        else:
            A.append(pots[-1])
        game(A, B, pots[:-1])


#gold_pots = [9, 8, 7, 5, 4, 6, 3, 1, 2]
#gold_pots = [1, 3, 4, 5, 1]
gold_pots = [1, 3, 4, 2, 6, 5]

A, B = [], []

total = sum(gold_pots)

game(A, B, gold_pots)
A_sum = sum(A)
print(A_sum , ' : ', total - A_sum)