문제 개요
여러 장의 카드가 한 줄로 나열되어 있고, 각 카드에는 고유한 점수가 부여되어 있습니다. 이 점수들은 정수 배열 cardPoints로 주어집니다. 매 단계마다 줄의 맨 앞 또는 맨 뒤에서 카드를 한 장씩 가져올 수 있으며, 정확히 k장을 가져와야 합니다. 최종 점수는 가져온 카드들의 점수 합이며, 목표는 얻을 수 있는 최대 점수를 찾는 것입니다.
예를 들어 cardPoints = [1,2,3,4,5,6,1], k = 3이 주어지면 출력은 12입니다. 첫 번째 선택 시 왼쪽 끝 카드를 가져가든 오른쪽 끝 카드를 가져가든 점수는 항상 1입니다. 그러나 오른쪽 끝부터 선택하는 전략이 총 점수를 극대화합니다. 즉, 가장 오른쪽 세 장을 가져오면 1 + 6 + 5 = 12라는 최종 점수를 얻습니다.
풀이 접근 방식
이 문제는 누적 합(prefix sum) 기법으로 효율적으로 해결할 수 있습니다. 왼쪽에서부터의 누적 합과 오른쪽에서부터의 누적 합을 미리 계산해 두면, '왼쪽에서 i장 + 오른쪽에서 (k−i)장'을 가져오는 모든 조합의 점수를 빠르게 비교할 수 있습니다.
구체적인 풀이 절차는 다음과 같습니다.
- 배열 v를 복사하여 두 개의 배열 pre1과 pre2를 만들고, ret := 0, n := v의 크기로 초기화합니다.
- i := 1부터 n−1까지 순회하며 pre1[i] += pre1[i−1]로 왼쪽 누적 합을 구성합니다.
- i := n−2부터 0까지 역순으로 순회하며 pre2[i] += pre2[i+1]로 오른쪽 누적 합을 구성합니다.
- k ≥ n이면 모든 카드를 가져올 수 있으므로 전체 합인 pre1[n−1]을 반환합니다.
- i := k−1로 설정하고 ret := pre1[i]로 초기화합니다. 이는 왼쪽에서만 k장을 가져오는 경우입니다.
- i를 하나 줄이고 j := n−1로 설정한 후, i ≥ 0인 동안 반복합니다.
- ret := max(ret, pre1[i] + pre2[j]) — 왼쪽에서 (i+1)장, 오른쪽에서 (n−j)장을 가져오는 조합을 검사합니다.
- i와 j를 각각 1씩 감소시킵니다.
- 마지막으로 ret := max(ret, pre2[n−k])로 오른쪽에서만 k장을 가져오는 경우도 확인합니다.
- ret을 반환합니다.
C++ 구현 예제
아래 구현 코드를 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxScore(vector<int>& v, int k) {
vector<int> pre1(v.begin(), v.end());
vector<int> pre2(v.begin(), v.end());
int ret = 0;
int n = v.size();
for (int i = 1; i < n; i++) {
pre1[i] += pre1[i - 1];
}
for (int i = n - 2; i >= 0; i--) {
pre2[i] += pre2[i + 1];
}
if (k >= n) {
return pre1[n - 1];
}
int i = k - 1;
ret = pre1[i];
i--;
int j = n - 1;
while (i >= 0) {
ret = max(ret, pre1[i] + pre2[j]);
i--;
j--;
}
ret = max(ret, pre2[n - k]);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5,6,1};
cout << (ob.maxScore(v, 3));
}입력
{1,2,3,4,5,6,1}출력
12
복잡도 분석
시간 복잡도는 배열을 두 번 순회하므로 O(n)이며, 공간 복잡도는 두 개의 누적 합 배열을 사용하므로 O(n)입니다. 참고로 슬라이딩 윈도우 기법을 활용하면 남겨두는 중간 구간의 합을 추적하는 방식으로 공간 복잡도를 O(1)까지 줄일 수 있습니다.