[Leetcode] 2218. Maximum Value of K Coins From Piles

문제 : https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/description/

---

테이블 위에 n개의 동전 더미가 있습니다. 각 더미는 여러 가지 단위의 양의 동전으로 이루어져 있습니다.

한 번의 이동으로 단일 더미에서 맨 위의 동전을 선택하여 제거하고 지갑에 추가할 수 있습니다.

piles는 각 더미를 나타내는 리스트이고, piles[i]는 i번째 더미의 위에서부터 아래쪽으로 순서대로 표시된 정수의 리스트입니다.

k개의 동전을 정확히 선택하여 최적으로 지갑에 보관할 경우, 지갑에 가질 수 있는 동전의 최대 총 가치를 반환하세요.

---

DP로 풀 수 있습니다.

 

먼저 dp에서 사용할 인덱스를 골라봅시다.

문제를 보았을 때 가장 먼저 골라볼 수 있는 인덱스가 될 수 있는 변수들은 더미(piles)의 수와 추가할 수 있는 동전 수(k) 입니다.

이들의 변수로 먼저 이차원 메모이제이션 용 배열을 만들어봅시다. dp[k][n].

 

이제 해당 배열에 뭘 저장해야 정답을 가져올 수 있는 점화식을 만들수있을지 추론해봅니다.

dp[k][n] = k개의 동전을 piles의 n개의 더미에서 가져올 때, 가능한 최대 총 가치.

위와 같이 정의하면 정답을 가져올 수 있습니다.

 

이제 대망의 점화식을 세워봅시다.

최대한 잘게 쪼개서 한 가지 경우만 생각해야 합니다.

k개의 동전을 n개의 더미가 아닌 k개의 동전을 n번째 더미에 우선적으로 가져온다고 가정합니다.

즉, 먼저 k개의 동전을 n번째 더미에서 모두 가져온다면, piles[n][0~k]의 합이 총 가치가 됩니다.

그 다음 가능한 경우는 k-1개의 동전을 n번째 더미에서 가져오는 경우입니다. 이 경우 2개의 동전은 나머지 더미(n-1개의 더미)에서 가져와야 하므로, piles[n][0~k-1] + dp[1][n-1] 가 됩니다.

k-2개의 동전을 n번째 더미에서 가져오는 경우도 비슷합니다. 이 경우 2개의 동전은 나머지 더미(n-1개의 더미)에서 가져와야 하므로, piles[n][0~k-2] + dp[2][n-1] 가 됩니다.

 

이를 반복하면 아래와 같은 점화식을 구할 수 있습니다.

dp[k][n] = max(piles[n]에서 위에서 i개 코인의 합 + dp[k-i][n-1]) 
           (0 <= i <= min(k, piles[i].length))

piles[n]에서 위에서 i개의 합은 부분합을 미리 구해두면 O(1)만에 구할 수 있습니다.

dp 배열을 모두 구했을 때, dp[k][n]이 정답이 됩니다.

 

M = piles[i].length 라 하였을 때, 시간복잡도는 O(NM).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/2218.%20Maximum%20Value%20of%20K%20Coins%20From%20Piles.cpp