두 명의 플레이어가 게임을 진행한다고 가정해 보겠습니다. 여러 개의 캔디가 한 줄로 놓여 있고, 1번 플레이어에게는 각 캔디의 점수 값을 나타내는 숫자 리스트 nums가 주어집니다. 각 플레이어는 자신의 차례에 줄 맨 앞에서 캔디를 1개, 2개 또는 3개 선택하여 리스트에서 제거하고, 해당 캔디들의 점수 합계를 자신의 점수에 더합니다. 모든 캔디가 제거되면 게임이 종료되며, 더 높은 점수를 가진 플레이어가 최종 승자가 됩니다. 우리가 확인해야 할 것은 1번 플레이어가 이 게임에서 승리할 수 있는지 여부입니다.
예를 들어 입력이 nums = [1, 1, 2, 3, 50]이라면 출력은 True가 됩니다. 1번 플레이어가 처음에 캔디 1개만 가져가면, 상대방은 규칙상 1개, 2개 또는 3개의 캔디를 가져와야 합니다. 어떤 선택을 하더라도 값이 50인 캔디는 결국 1번 플레이어의 몫이 되기 때문입니다.
문제 해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '현재 위치에서 시작하는 플레이어가 얻을 수 있는 최대 점수 차이'를 바텀업 방식으로 계산하는 것입니다.
다음 단계를 따릅니다 −
- n := nums의 크기
- table := 0으로 초기화된 길이 3짜리 배열 (최근 3개의 결과만 저장하여 공간을 절약)
- i를 n−1부터 0까지 1씩 감소시키며 반복:
- profit := −inf (음의 무한대로 초기화)
- sum_val := 0
- j를 i부터 min(i+3, n)까지 반복:
- sum_val := sum_val + nums[j] (현재 차례에 가져가는 캔디의 누적 점수)
- profit := profit과 (sum_val − table[j−i]) 중 최댓값 (상대방이 이후에 얻을 점수를 차감)
- table := [profit, table[0], table[1]]로 갱신
- table[0] > 0이면 True 반환, 그렇지 않으면 False 반환
여기서 table 배열은 현재 위치에서 시작한 플레이어가 상대방보다 얼마나 더 많은 점수를 얻을 수 있는지를 저장합니다. 마지막 위치에서 거꾸로 계산해 나가기 때문에, 최종적으로 table[0]이 양수라면 1번 플레이어(선공)가 반드시 이길 수 있다는 의미입니다.
예제 구현
아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다 −
import math
class Solution:
def solve(self, nums):
n = len(nums)
table = [0, 0, 0]
for i in range(n - 1, -1, -1):
profit = -math.inf
sum_val = 0
for j in range(i, min(i + 3, n)):
sum_val += nums[j]
profit = max(profit, sum_val - table[j - i])
table[:] = [profit, table[0], table[1]]
return table[0] > 0
ob = Solution()
nums = [1, 1, 2, 3, 50]
print(ob.solve(nums))
입력
[1, 1, 2, 3, 50]
출력
True
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)입니다. 각 위치 i에 대해 최대 3번의 내부 반복만 수행하기 때문입니다. 공간 복잡도 역시 길이 3짜리 배열 하나만 사용하므로 O(1)로 매우 효율적입니다. 전체 캔디의 개수가 많아져도 성능 저하 없이 빠르게 승패를 판단할 수 있습니다.