알고리즘 문제/Leetcode
[Leetcode] 1423. Maximum Points You Can Obtain from Cards
햄과함께
2022. 6. 26. 15:56
320x100
문제 : 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.
그림 보면 이해하실거라 생각합니다.
예시의 답은 [그림2]의 14.
시간복잡도는 O(k)
320x100