문제 개요
candies라는 숫자 리스트가 주어지고, 두 명의 플레이어가 누가 더 많은 사탕을 모으는지 겨루는 게임이 있다고 가정해 보겠습니다. 이 게임은 턴제로 진행되며, 1번 플레이어가 먼저 시작합니다. 각 턴마다 플레이어는 리스트의 맨 앞 또는 맨 뒤에 있는 사탕 중 하나를 가져갈 수 있습니다. 우리가 확인해야 할 것은 1번 플레이어가 최적의 전략을 사용했을 때 상대방보다 더 많은 사탕을 모을 수 있는지 여부입니다.
예를 들어 입력이 candies = [1, 4, 3, 8]이라면 결과는 True가 됩니다. 1번 플레이어가 첫 턴에 맨 뒤의 8개짜리 사탕을 가져가면, 이후 2번 플레이어가 1을 선택하든 3을 선택하든 관계없이 1번 플레이어는 남은 사탕을 가져가 승리할 수 있기 때문입니다.
접근 방법: 미니맥스(Minimax) 전략
이 문제는 게임 이론의 관점에서 접근할 수 있습니다. 핵심 아이디어는 현재 구간 [left, right]에서 현재 차례인 플레이어가 상대방 대비 얻을 수 있는 최대 점수 차이를 재귀적으로 계산하는 것입니다.
N := candies 리스트의 길이로 설정합니다.
difference(left, right) 함수를 정의합니다. 이 함수는 구간 내에서 현재 차례 플레이어가 확보할 수 있는 최선의 점수 차이를 반환합니다.
left와 right가 같다면(사탕이 하나만 남은 경우) candies[left]를 그대로 반환합니다.
그렇지 않다면 두 가지 선택지를 비교하여 더 큰 값을 반환합니다.
• 맨 앞 사탕을 가져가는 경우: candies[left] − difference(left + 1, right)
• 맨 뒤 사탕을 가져가는 경우: candies[right] − difference(left, right − 1)메인 로직에서는 difference(0, N − 1)의 값이 0보다 크면 True, 그렇지 않으면 False를 반환합니다.
여기서 음수 값이 나오는 이유는 상대방도 최적의 전략으로 플레이하기 때문입니다. 즉, 내가 사탕을 하나 가져가면 남은 구간에서는 상대가 유리한 차이만큼 벌게 되므로, 이를 빼주는 방식으로 서로의 이득을 반영합니다.
구현 예제
class Solution: def solve(self, candies): N = len(candies) def difference(left, right): nonlocal candies if left == right: return candies[left] return max(candies[left] − difference(left + 1, right), candies[right] − difference(left, right − 1)) return difference(0, N − 1) > 0 ob = Solution() candies = [1, 4, 3, 8] print(ob.solve(candies))
입력
[1, 4, 3, 8]
출력
True
복잡도 분석 및 참고 사항
위 재귀 풀이의 시간 복잡도는 O(2^N)으로, 리스트의 길이가 길어지면 비효율적일 수 있습니다. 실전에서는 메모이제이션(memoization)을 적용하여 이미 계산한 (left, right) 구간의 결과를 캐싱하면 시간 복잡도를 O(N²)까지 줄일 수 있습니다. 또한 동일한 문제는 동적 계획법(DP) 테이블을 활용한 반복문 방식으로도 해결 가능합니다.