두 명의 플레이어가 게임을 하고 있다고 가정합니다. 여러 개의 사탕을 한 줄에 놓고 사람 1에게 각 사탕의 포인트 값을 나타내는 nums라는 숫자 목록이 제공됩니다. 각 사람의 차례에 줄 맨 앞에서 1, 2 또는 3개의 사탕을 선택한 다음 목록에서 삭제하고 점수의 합을 점수에 추가할 수 있습니다. 이 게임은 모든 사탕이 삭제되면 종료되며 더 높은 점수를 받은 사람이 승자가 됩니다. 1번 사람이 이 게임에서 이길 수 있는지 확인해야 합니다.
따라서 입력이 nums =[1, 1, 2, 3, 50]과 같으면 사람 1이 사탕 1개를 가져갈 수 있고 다른 플레이어는 사탕 1, 2 또는 3개를 가져와야 하므로 출력은 True가 됩니다. 어쨌든 사람 1은 50의 값을 가진 사탕을 받을 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=숫자 크기
-
table :=0이 세 개인 배열.
-
n − 1에서 0 사이의 i에 대해 1만큼 감소합니다.
-
이익 :=-inf
-
sum_val :=0
-
범위 i에서 최소 i + 3 및 n까지의 j에 대해 수행
-
sum_val :=sum_val + nums[j]
-
이익 :=이익의 최대값 및 (sum_val − table[j − i])
-
-
set table :=세 가지 값이 있는 목록 [profit, table[0], table[1]]
-
-
table[0]> 0이면 true를 반환하고, 그렇지 않으면 false
를 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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