Python으로 스톤 게임 최대 점수 구하기: DFS와 부분합 활용법

문제 소개

여러 개의 돌이 한 줄로 놓여 있고, 각 돌에는 배열 stoneValue에 담긴 숫자 값이 하나씩 매겨져 있다고 가정해 보겠습니다. 매 라운드마다 Amal은 돌 줄을 두 부분으로 나누고, Bimal은 각 부분의 값, 즉 해당 부분에 속한 모든 돌 값의 합을 계산합니다. 그다음 Bimal은 값이 더 큰 부분을 버리고, 남은 부분의 값만큼 Amal의 점수가 증가합니다. 두 부분의 값이 같을 경우에는 Amal이 직접 어느 쪽을 버릴지 결정할 수 있습니다. 다음 라운드는 남은 부분에서 다시 시작되며, 돌이 하나만 남으면 게임이 끝납니다. 우리가 구해야 하는 것은 Amal이 얻을 수 있는 최대 점수입니다.

예제로 이해하기

입력이 stoneValue = [7,3,4,5,6,6]일 때 출력은 24입니다.

라운드 1: Amal은 돌 줄을 [7,3,4]와 [5,6,6]으로 나눕니다. 왼쪽의 합은 14, 오른쪽의 합은 17입니다. Bimal은 값이 더 큰 오른쪽을 버리고, Amal의 점수는 14가 됩니다.
라운드 2: Amal은 남은 줄을 [7]과 [3,4]로 나눕니다. 양쪽의 합이 모두 7로 같으므로 Amal이 결정권을 갖게 되며, 이후 진행을 고려하면 왼쪽 [7]을 버리는 것이 유리합니다. Amal의 점수는 (14 + 7) = 21이 됩니다.
라운드 3: Amal은 [3]과 [4]로 나눌 수밖에 없습니다. Bimal은 값이 큰 오른쪽 [4]를 버리고, Amal의 점수는 (21 + 3) = 24로 확정됩니다.

풀이 접근 방식

이 문제는 깊이 우선 탐색(DFS)과 부분합(partial sum) 배열을 함께 사용하면 깔끔하게 해결할 수 있습니다. 전체 흐름은 다음과 같습니다.

구간 [start, end]를 처리하는 dfs() 함수를 정의합니다.
start >= end이면 더 이상 나눌 수 없으므로 0을 반환합니다.
max_score := 0으로 초기화합니다.
cut을 start부터 end-1까지 반복하며 다음을 수행합니다.
- sum1 := partial_sum[start][cut] (왼쪽 부분의 합)
- sum2 := partial_sum[cut+1][end] (오른쪽 부분의 합)
- sum1 > sum2이면: score := sum2 + dfs(cut+1, end)
- sum1 < sum2이면: score := sum1 + dfs(start, cut)
- 두 값이 같으면: score := sum1 + max(dfs(start, cut), dfs(cut+1, end))
- max_score := max(score, max_score)
max_score를 반환합니다.

부분합 배열은 getPartialSum() 함수를 통해 미리 계산해 둡니다. 먼저 대각선 요소에 각 돌의 값을 저장한 뒤, partial_sum[i][j] = partial_sum[i][j-1] + stoneValue[j] 점화식으로 누적합을 채워 넣으면 임의 구간의 합을 상수 시간에 구할 수 있습니다.

Python 구현 코드

def solve(stoneValue):
    def dfs(start, end):
        if start >= end:
            return 0
        max_score = 0
        for cut in range(start, end):
            sum1 = partial_sum[start][cut]
            sum2 = partial_sum[cut+1][end]
            if sum1 > sum2:
                score = sum2 + dfs(cut+1, end)
            elif sum1 < sum2:
                score = sum1 + dfs(start, cut)
            else:
                score = sum1 + max(dfs(start, cut), dfs(cut+1, end))
            max_score = max(score, max_score)
        return max_score

    def getPartialSum():
        for i in range(n):
            partial_sum[i][i] = stoneValue[i]
        for i in range(n):
            for j in range(i+1, n):
                partial_sum[i][j] = partial_sum[i][j-1] + stoneValue[j]

    n = len(stoneValue)
    partial_sum = [[0]*n for _ in range(n)]
    getPartialSum()
    return dfs(0, n-1)

stoneValue = [7,3,4,5,6,6]
print(solve(stoneValue))

입력 및 실행 결과

입력:

[7,3,4,5,6,6]

출력:

성능 최적화 팁

위 구현은 동일한 구간을 여러 번 다시 계산할 수 있어 입력 크기가 커지면 비효율적입니다. dfs() 정의 위에 @lru_cache(maxsize=None) 데코레이터를 붙여 메모이제이션을 적용하면 중복 호출이 제거되어 시간 복잡도를 O(n³) 수준으로 낮출 수 있습니다.