문제 개요
Amal과 Bimal이 벽돌 게임을 하고 있다고 가정해 보겠습니다. 두 사람에게는 각 벽돌 위에 숫자가 적혀 있는 n개의 벽돌 배열 nums가 주어집니다. 게임 규칙은 다음과 같습니다.
- 두 플레이어는 번갈아 가며 맨 위에서 벽돌을 한 개, 두 개 또는 세 개씩 제거할 수 있습니다.
- 제거한 벽돌에 적힌 숫자가 해당 플레이어의 점수에 더해집니다.
- 항상 Amal이 먼저 시작합니다.
이때 Amal이 확보할 수 있는 최대 점수를 구하는 것이 목표입니다.
동작 예시
예를 들어 입력이 nums = [1,2,3,4,5]라면 결과는 6입니다.
Amal은 첫 차례에 벽돌 {1}, {1,2}, {1,2,3} 중 하나를 제거할 수 있습니다.
- 처음 두 개 또는 세 개를 가져가면 Bimal이 남은 벽돌을 모두 가져가 더 많은 점수를 얻게 됩니다.
- 반면 Amal이 처음에 1만 가져가면, Bimal은 최대 {2,3,4} = 9를 가져갈 수 있고, 그러면 Amal은 마지막 벽돌 5를 가져갈 수 있습니다.
따라서 Amal의 총점은 1 + 5 = 6이 됩니다.
풀이 접근 방식
이 문제는 동적 계획법(DP) 아이디어로 접근할 수 있습니다. 리스트를 뒤집으면 마지막 상황부터 차례로 살펴볼 수 있어, 각 시점에서 한 번에 가져갈 수 있는 세 가지 경우(1개, 2개, 3개)를 비교하며 최적의 선택을 누적하기가 쉬워집니다. 해결 단계는 다음과 같습니다.
- INF := 9999 로 초기화합니다.
- n := nums의 크기
- 리스트 nums를 뒤집습니다.
- temp := 크기가 n이고 0으로 채워진 배열
- total := 크기가 n이고 0으로 채워진 배열
- nums의 각 인덱스 i와 값 val에 대해 다음을 수행합니다.
- total[i] := total[i-1] + val
- temp[0] := nums[0]
- temp[1] := temp[0] + nums[1]
- temp[2] := temp[1] + nums[2]
- i를 3부터 n-1까지 반복하면서 다음을 수행합니다.
- a := nums[i]
- b := nums[i] + nums[i-1]
- c := nums[i] + nums[i-1] + nums[i-2]
- temp[i] := a, b, c 중 최댓값
- temp[n-1]을 반환합니다.
구현 예시
아래 구현을 통해 더 자세히 이해해 보겠습니다.
INF = 99999
def solve(nums):
n = len(nums)
nums.reverse()
temp = [0]*n
total = [0]*n
for i, val in enumerate(nums):
total[i] = total[i-1] + val
temp[0] = nums[0]
temp[1] = temp[0] + nums[1]
temp[2] = temp[1] + nums[2]
for i in range(3, n):
a = nums[i]
b = nums[i] + nums[i-1]
c = nums[i] + nums[i-1] + nums[i-2]
temp[i] = max(a, b, c)
return temp[n-1]
nums = [1,2,3,4,5]
print(solve(nums))
입력
[1,2,3,4,5]
출력
6
복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 길이 n의 보조 배열 temp와 total 두 개를 사용하므로 공간 복잡도 역시 O(n)입니다.