[Leetcode] 1423. Maximum Points You Can Obtain from Cards

문제 : https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

---

여러 장의 카드가 한 줄로 배열되어 있다. 각 카드에는 연관된 점수가 있다. 이 배열을 cardPoints라 한다.

한 단계에서 배열의 가장자리, 최좌측, 최우측 중 한 곳에서 한 장의 카드를 가져올 수 있다. 

총 k번의 단계를 거쳐, 총 k개의 카드를 가져와야 한다고 할 때 얻을 수 있는 최대 점수를 구해라.

---

오른쪽으로 부터 k개의 합을 구해둔뒤, 왼쪽부터 선택하는 카드 수를 0부터 k개까지 탐색하면서 나올 수 있는 점수들의 합을 구한 뒤 이들 중 최대값이 정답이 된다.

예시 cardPoints = [4, 3, 1, 9, 1], k = 3.

[그림1] 11

[그림2] 14

[그림3] 8

[그림4] 8

그림 보면 이해하실거라 생각합니다.

예시의 답은 [그림2]의 14.

 

시간복잡도는 O(k)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1423.%20Maximum%20Points%20You%20Can%20Obtain%20from%20Cards.cpp