1. 문제
https://www.acmicpc.net/problem/11062
2. 문제 이해
카드 n장이 일렬로 주어집니다.
카드 양쪽 끝 두 장 중에 한 장을 골라 가져옵니다.
점수는 카드에 적혀있는 숫자를 계속해서 누적합니다.
번갈아가며 카드가 모두 없어질 때까지 반복합니다.
최종적으로 점수가 더 높은 사람이 승리합니다.
3. 해결 방법
가. DP 가능성 확인
브루트포스로 해결할 경우 시간 복잡도가 \(O(2^{N})\) 으로 N의 최대값이 1000이기 때문에 불가능합니다.
그리디로 해결 가능하다면 \(O(N)\) 만에 해결 가능합니다. 하지만 위의 예시처럼 매 순간 최선의 선택을 할 경우, 큰 수를 가진 카드가 언제 나올지 모르기 때문에 그리디로 해결할 수 없습니다.
이 문제를 DP로 풀 수 있는지 확인하기 위해 Overlapping Subproblems(겹치는 부분 문제)와 Optimal Substructure(최적 부분 구조)를 가지고 있는지 확인해봅시다.
먼저, 카드의 개수가 줄어들어도 계속해서 주어진 카드의 양 끝 중 하나만 선택해야하므로 Overlapping Subproblems에 해당합니다.
다음으로, Optimal Substructure를 가지는지 확인해봅시다.
2, 9, 20의 카드가 있을 경우, 가장 작은 부분 구조로 2, 9, 20이 각각 한 장씩 있다고 가정했을 경우 선공:후공 최적해는 2:0, 9:0, 20:0입니다.
그 다음 확대해서 2, 9 두 장이 있다고 가정하면 2:0에서 선공이 9를 가져가면 선공:후공이 9:2, 9:0에서 2를 선공이 가져가면 2:9가 가능하고 이 때는 선공:후공은 9:2가 최적해가 됩니다. 같은 방법으로 9, 20 두 장을 살펴보면 최적해는 20:9가 됩니다.
더 확대해서 2, 9, 20을 살펴보면, 9:2와 20에서 선공이 20을 가져가면 후공이 9, 선공이 2가 되므로 22:9가 되고, 20:9와 2에서 선공이 2를 가져가면 후공이 20, 선공이 9가 되므로 11:20이 돼서 선공:후공은 22:9가 최적해가 됩니다.
이처럼 부분 문제의 최적해가 더 큰 문제의 최적해를 구하는데 사용되므로 Optimal Substructure를 가집니다.
나. DP 테이블
이제 위에서 살펴본 과정을 DP 테이블을 차근차근 채워가며 문제를 풀어봅시다.
특정 범위에서의 최적해를 관리해야하므로, 2차원 배열을 이용하여 DP 테이블을 구성합니다.
가장 먼저 범위가 1(카드가 1장)인 경우부터 시작하면 아래와 같이 채울 수 있습니다.
범위를 1 늘려가며 반복하면 아래와 같은 과정을 거쳐 완성됩니다.
다. 개선하기
위와 같이 DP 테이블을 관리하려면 자료구조로 3차원 배열(시작, 끝, 선후)이 필요합니다.
두 점수의 합계는 해당하는 범위 내의 모든 카드의 숫자를 합한 값과 같습니다.
이 점을 이용하면 두 점수를 배열로 관리하는 대신 카드 값의 누적합을 관리하면서 한 점수만 관리할 수 있습니다.
위와 같이 3차원 배열을 2차원 배열로 개선하여 관리할 수 있습니다.
