[Kickstart][2020][Round A] 2. Plates

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb

---

N개의 접시 스택이 주어지고, 각 접시들은 각 스택마다 K개의 접시들로 이루어진다.

각 접시들은 양의 정수를 가지고 있으며 접시들은 쌓여 있으므로 위에 있는 접시들부터 차례대로 가져올 수 있다. (중간에 있는 접시만 가져올수는 없다.)

최대 P개의 접시들로 저녁을 구성하려고 할 때, 해당 접시들의 양의 정수의 합이 최대가 되는 경우를 구하라. (최대 접시들의 고유 값의 합 리턴)  

---

탐색은 dfs로 하고 메모이제이션을 위해 dp를 사용했다.

n번째 접시 스택부터 N번빼 접시 스택까지 접시를 선택할 수 있다고 할 때, 총  P-p개의 접시로 얻을 수 있는 양의 정수 합의 최대값을 2차원 배열에 저장한다. (dp[n][p])

dp[n][p] = max(
	dp[n+1][p+i] + n번째 접시 스택을 위에서부터 i개 선택했을 때 접시 정수 합 // i = 0~K
)

점화식은 위 식과 같아진다.

메모이제이션을 사용하기 위해서 dp[n][p]가 n번째 접시 스택까지 접시를 선택할 때, p개의 접시로 얻을 수 있는 양의 정수가 아닌, N-n, P-p 를 사용했다.

 

시간복잡도는 O(NPK)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundA/2.%20Plates.cpp