문제 개요
카드 게임을 하고 있다고 가정해 보겠습니다. 각 카드마다 숫자가 적혀 있고, 이 카드들이 일렬로 나열되어 있으며 숫자는 무작위로 배치되어 있습니다. 또한 카드 목록의 맨 앞과 맨 끝에는 숫자 1이 적힌 카드가 하나씩 추가됩니다. 게임의 목표는 주어진 카드들을 골라 수집하여 최대한 많은 포인트를 얻는 것입니다.
카드는 배열 cards로 표현되며, 배열의 각 원소는 해당 위치 카드에 적힌 숫자를 의미합니다. i번째 카드를 집으면 cards[i - 1] * cards[i] * cards[i + 1]만큼의 포인트를 얻습니다. 카드를 집으면 해당 카드는 사라지고, 양옆에 있던 카드들이 서로 새로운 이웃이 됩니다. 이처럼 주어진 카드들로부터 수집할 수 있는 최대 포인트를 구하는 것이 문제입니다.
예시 이해하기
예를 들어 입력이 cards = [7, 5, 9, 10]이라면 출력은 1025가 됩니다. 게임에서 다음과 같은 순서로 카드를 집을 수 있습니다.
- 인덱스 1의 카드를 집어 7 × 5 × 9 = 315포인트 획득
- 새로 생긴 인덱스 1의 카드를 집어 7 × 9 × 10 = 630포인트 획득
- 인덱스 1의 카드를 집어 7 × 10 = 70포인트 획득
- 마지막 남은 카드를 집어 10포인트 획득
따라서 총 포인트는 315 + 630 + 70 + 10 = 1025입니다.
해결 접근 방식
이 문제는 구간을 분할하며 재귀적으로 탐색하는 방식으로 해결할 수 있습니다. 핵심 아이디어는 특정 구간 (x, y) 안에서 z번째 카드를 가장 마지막에 집는다고 가정하면, 그 시점의 포인트가 cards[x] * cards[z] * cards[y]가 된다는 점입니다. 왼쪽 구간과 오른쪽 구간을 각각 재귀적으로 처리하면서 얻을 수 있는 최댓값을 구하면 됩니다.
구체적인 알고리즘은 다음과 같습니다.
- 매개변수 x, y를 받는 search() 함수를 정의합니다.
- temp를 0으로 초기화합니다.
- z를 x + 1부터 y - 1까지 반복하면서 temp를 다음 값 중 최댓값으로 갱신합니다: search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y]
- temp를 반환합니다.
- cards 리스트의 맨 앞과 맨 끝에 각각 1을 삽입합니다.
- search(0, len(cards) - 1)의 결과를 반환합니다.
구현 예제
아래 파이썬 구현을 통해 더 잘 이해해 보겠습니다.
def solve(cards):
def search(x, y):
temp = 0
for z in range(x + 1, y):
temp = max(temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y])
return temp
cards = [1] + cards + [1]
return search(0, len(cards) - 1)
print(solve([7, 5, 9, 10]))
입력
[7, 5, 9, 10]
출력
1025
성능 개선 팁
위 구현은 단순 재귀 호출을 사용하므로 동일한 구간이 여러 번 계산될 수 있습니다. functools.lru_cache 데코레이터를 활용해 메모이제이션을 적용하면 중복 연산을 제거할 수 있으며, 시간 복잡도를 O(n³) 수준으로 낮춰 더 큰 입력에서도 효율적으로 동작하게 만들 수 있습니다.