동전 게임

• 돌을 가져가는 갯수의 제한은 피보나치 님과 같은 규칙인데, 돌마다 점수가 부여되고 가져간 돌의 점수를 최대화하는 스코어링 게임이다.
• 남은 돌의 갯수가 같아도 최대로 가져갈수 있는 돌의 갯수가 다르면 얻을수 있는 점수가 다르다. 따라서 남은돌의 갯수와 최대로 가져갈수 있는 돌의 갯수를 함께 묶은 것을 포지션으로 생각해야 한다.
• 이것을 minimax DP로 계산하는것 자체는 전형적이다. 제로섬 게임이므로 각 포지션에서 얻을수 있는 최대 점수만 관리하면 계산이 가능하다
• 하지만 이렇게 단순하게 구현하면, 포지션의 갯수는 O(n^2)개가 되고, 각 포지션에서 취할수 있는 액션의 갯수가 O(n)개가 되므로 총 O(n^3)의 시간복잡도가 나오는데, n이 최대 2000이므로 시간내에 돌릴수 없다.
• 돌이 n개가 남아있고 최대 k개를 가져갈수 있을때 얻을수 있는 최대 점수를 dp[n][k]라고 하자. dp[n][k+1]은 1,2,…,k+1개를 가져갔을때의 스코어를 각각 모두 계산해서 최댓값을 구하는 대신에, dp[n][k]과 k+1개를 가져갔을때의 스코어, 두 값의 최댓값으로 빠르게 구할수 있다. 이렇게 계산하면, dp테이블의 각 원소들을 O(1)에 계산 가능하므로, 전체 시간복잡도를 O(n^2)으로 줄일수 있고, 이제 시간적으로는 여유있게 돌릴수 있다.
• 하지만 여기서 끝이 아닌데.. 이 문제에서는 메모리 제한이 32MB으로 매우 작게 잡혀있어서 메모리 면에서도 고민이 필요하다. 파이썬 기준으로 n*n 크기의 dp배열을 만들면 메모리 초과를 받는다.
• 한가지 해결책은 PyPy를 사용하는 것이다. pypy는 메모리 제한이 조금더 널널하기 때문에 (물론 기본적으로 쓰는 메모리가 훨씬 많기는 하지만), n*n 크기의 배열을 만들어서 사용해도 메모리 제한에 걸리지 않았다.
• 하지만 메모리 커팅을 좀더 한다면 python으로도 통과시킬수 있다. 일단 k가 n보다 큰 경우는 의미가 없기 때문에, 그 경우에 대한 메모리를 줄이면 대략 n*n/2 크기의 배열이 되긴 하지만, 이것으로는 충분치 않다.
• 조금 더 관찰하면 메모리를 줄일 여지가 몇가지 보이는데, 우선 현재 턴에 가져갈수 있는 최대 갯수 k는, 항상 짝수로 주어진다. 따라서 dp테이블에서도 k가 짝수인 경우만 저장하면 되므로 다시 메모리를 절반으로 줄일수 있다.
• 다른 관찰은, k가 n/3보다 큰 경우이다. 내 턴에서 n/3 이상의 돌을 가져갈 경우에 다음턴에 상대방은 무조건 남은 돌을 몽땅 다 가져가게 된다. 즉, n/3 이상을 가져갈때에는 최대한 많이 가져가는 것만이 유의미한 행동이다. 이렇게 x개를 가져가면 이번턴에 맨위 x개 돌에 해당하ㅡㄴ 점수를 얻고 그 이후에는 점수를 못얻게 되므로 최대 스코어도 dp값을 건드리지 않고 계산할수 있다. 그래서 k가 n/3보다 큰 경우의 최대 스코어는 max(dp[n][n/3], sum(value[n-k:n]) 과 같은 형태로 계산이 가능하다. 따라서 dp 테이블에서도 각 n에 대해서 n/3 까지만 저장하면 되므로 메모리를 1/3로 줄일수 있다.
• 이렇게 두가지 아이디어가 있었지만, 1/3로 줄이는 두번째 방법만 적용해서 구현해도 통과가 되었기에, 절만으로 줄이는 첫번째 아이디어는 적용하지 않았다. 그리고 물론 이것을 적용하면 실행시간도 당연히 줄어들게 된다.

"""Solution code for "BOJ 6000. 동전 게임".

- Problem link: https://www.acmicpc.net/problem/6000
- Solution link: http://www.teferi.net/ps/problems/boj/6000

Tags: [game theory]
"""

import sys

INF = float('inf')


def main():
    N = int(sys.stdin.readline())
    C = [int(sys.stdin.readline()) for _ in range(N)]

    max_score = [[None] * (N + 1) for _ in range(N + 1)]
    max_score[0][0] = 0
    coin_sum = 0
    for i in range(1, N + 1):
        coin_sum += C[-i]
        min_max_score = INF
        for k in range(1, i + 1):
            opponent_max_score = max_score[i - k][min(i - k, k * 2)]
            if opponent_max_score < min_max_score:
                min_max_score = opponent_max_score
            max_score[i][k] = coin_sum - min_max_score

    print(max_score[N][2])


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 6000. 동전 게임".

- Problem link: https://www.acmicpc.net/problem/6000
- Solution link: http://www.teferi.net/ps/problems/boj/6000

Tags: [game theory]
"""

import sys

INF = float('inf')


def main():
    def get_max_score(n, k):
        if k * 3 >= n:
            return max(max_score[n][-1], psum[n] - psum[n - k])
        else:
            return max_score[n][k]

    N = int(sys.stdin.readline())
    C = [int(sys.stdin.readline()) for _ in range(N)]
    psum = [v := 0] + [v := v + x for x in reversed(C)]

    max_score = [[0] for _ in range(N + 1)]
    coin_sum = 0
    for i in range(1, N + 1):
        coin_sum += C[-i]
        min_max_score = INF
        for k in range(1, i // 3 + 1):
            opponent_max_score = get_max_score(i - k, k * 2)
            if opponent_max_score < min_max_score:
                min_max_score = opponent_max_score
            max_score[i].append(coin_sum - min_max_score)

    print(get_max_score(N, 2))


if __name__ == '__main__':
    main()