문제 : 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).
'알고리즘 문제 > Leetcode' 카테고리의 다른 글
[Leetcode] 1768. Merge Strings Alternately (0) | 2023.04.18 |
---|---|
[Leetcode]1431. Kids With the Greatest Number of Candies (0) | 2023.04.17 |
[Leetcode] 516. Longest Palindromic Subsequence (0) | 2023.04.14 |
[Leetcode] 71. Simplify Path (0) | 2023.04.12 |
[Leetcode] 2390. Removing Stars From a String (0) | 2023.04.11 |
댓글