[코딩 인터뷰][HackerRank] Bricks Game

※ 이 포스트는 HackerRank 문제인 Bricks Game 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, HackerRank에서의 Submission 통과만을 보장합니다.

Bricks Game

문제 출처 : https://www.hackerrank.com/challenges/play-game/problem
카테고리 : Dynamic Programming
난이도 : Middle (55 point)

문제 설명

수열이 배열 형태로 주어진다. 두 플레이어는 자신의 턴에 수열에 남아있는 수를 앞에서부터 1 ~ 3개를 가져갈 수 있다. 예를 들어 [1, 2, 3, 4, 5]라는 수열이 주어진다면 첫 번째 플레이어는 1이나 1, 2나 1, 2, 3을 가져갈 수 있는 것이다. 이 방식으로 턴을 진행하다가 남은 수가 없어지면 게임이 종료된다. 점수는 각 플레이어가 가져간 수의 합이다. 두 플레이어가 최선을 다한다고 할 때, 첫 번째 플레이어가 가져갈 수 있는 수의 최대값은 무엇일까.

위 예제에서 첫 번째 플레이어가 얻을 수 있는 점수의 최대값은 6이다. 첫 턴에 1을 가져가고 마지막 턴에 5를 가져가거나, 첫 턴에 1 2 3을 가져가는 경우다.

문제 풀이

역으로 끝에서부터 계산해나가는 전략을 사용한다. DP라는 배열을 사용할 것이다. DP[i][j]는 남은 수열의 맨 앞 인덱스가 ‘i’인 상황에서 플레이어 ‘j’가 턴을 가지고 있을 때 플레이어 ‘j’가 얻을 수 있는 점수의 최대값을 저장한다. 계산을 역순으로 진행하기 때문에 DP[i – 1][0]을 계산하는 시점에서 DP[i]는 이미 계산되어 있다.

DP[i][0]을 계산한다고 생각해보자. 이 값은 어떻게 얻을 수 있을까? 이 시점에서 플레이어 0이 할 수 있는 동작은 3가지다. 1개를 가져가거나, 2개를 가져가거나, 3개를 가져가거나. 그 다음 턴은 플레이어 1에서 넘어간다. 이 시점에서 플레이어 1이 가장 최선을 전략을 사용할 경우에, 플레이어 1이 얻는 결과는 DP[i + 1][1], DP[i + 2][1], DP[i + 3][1] 중 하나가 된다. 이 셋 중 어떤 미래를 맞이할지는 플레이어 0이 가져가는 숫자의 갯수에 달려있다.

수열 Arr의 인덱스 i부터 끝까지 수의 합을 Sum이라고 하자. 만약 플레이어 0이 Arr[i]를 맨 앞에 둔 상태에서 숫자를 하나만 가져간다고 할 때, 남은 게임을 최적의 전략을 택한다면, Sum – DP[i + 1][1]만큼의 점수를 얻는다. 전체 점수에서 상대 플레이어가 가져가는 점수를 뺀 만큼이 내 점수가 되는 것이니까. 그렇다면 플레이어 0은 Sum – DP[i + 1][1], Sum – DP[i + 2][1], Sum – DP[i + 3][1] 중에서 가장 최댓값을 얻을 수 있는 곳을 선택할 것이다. 이 값이 DP[i][0]이 된다. 플레이어 1에 대해서도 동일한 전략을 취해주면 된다.

이 과정이 끝난 후 DP[0][0]은 맨 처음의 수열에서 플레이어 0이 턴을 잡을 때 얻을 수 있는 점수의 최댓값을 가진다. 이 값을 리턴하면 된다.

코드

#!/bin/python

from __future__ import print_function

import os
import sys

#
# Complete the bricksGame function below.
#
def bricksGame(arr):
    DP = []
    N = len(arr)
    for i in range(N + 1):
        DP.append([0, 0])
    Sum = 0
    for i in range(N - 1, -1, -1):
        Sum += arr[i]
        for j in range(1,4):
            if i + j <= N:
                DP[i][0] = max(DP[i][0], Sum - DP[i + j][1])
                DP[i][1] = max(DP[i][1], Sum - DP[i + j][0])
    return DP[0][0]
    #
    # Write your code here.
    #

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(raw_input())

    for t_itr in xrange(t):
        arr_count = int(raw_input())

        arr = map(int, raw_input().rstrip().split())

        result = bricksGame(arr)

        fptr.write(str(result) + '\n')

    fptr.close()

코딩 인터뷰 – Bricks Game