[leetcode][920] Number of Music Playlists

문제 : https://leetcode.com/problems/number-of-music-playlists/

---

DP로 풀었다.

dp[N][L] = N개의 노래로 L개의 노래가 있는 플레이 리스트를 만드는 경우의 수.

만약 i개의 노래로 j개의 노래가 있는 플레이 리스트를 만들었다고 할 때(dp[i][j]) 다음에 추가하는 노래는 플레이리스트에 없는 노래거나  플레이리스트에 이미 있는 노래. 이렇게 2가지 경우가 있다.

플레이리스트에 없는 노래를 추가한다면 만들어지는 dp배열은 dp[i+1][j+1]이다. (노래가 하나 추가되고 플레이리스트도 하나 느므로)

dp[i][j]가 추가될 수 있는 노래의 개수(N - i = 전체 - 이미 들은 노래)만큼 추가되므로 dp[i+1][j+1] += dp[i][j] * (N - i) 이다.

ex) N = 3, i = 1, j = 1 일 때 만들어져있는 배열은 [1], [2], [3] 일 것이고 새로운 노래들이 추가한다고 하면 각 배열에서 없는 노래가 추가 될 것이다. 

즉, 추가된 배열은 [1, 2],[1, 3], [2, 1],[2, 3], [3, 1],[3, 2] 가 된다. 

여기에서 각 배열에서 없는 노래 수가 2이고 이미 만들어져 있던 배열 수가 3이므로 총 3(dp[i][j]) * 2(N - i) = 6이 된다.

플레이리스트에 있는 노래를 추가한다면 dp[i][j+1]이다. (노래의 개수는 그대로 이고 플레이리스트는 하나 느므로)

dp[i][j]가 추가될 수 있는 노래의 개수는 아까와 마찬가지로 N-i라고 생각할수도 있지만 여기에서 K를 생각해봐야 한다.

두 번째 조건에서 이미 나온 노래는 다른 종류의 노래가 K개 만큼 틀어진 뒤에야 다시 틀 수 있다고 정의했다.

따라서 이미 플레이된 i개의 노래 중 K개는 틀 수 없다.

즉, dp[i][j+1] += dp[i][j] * (i - K)가 된다.

ex) 만들어져 있는 플레이리스트를 [1, 2, 3, 4] 이라 생각해보자. i = 4, j = 4 let) K = 2.

이미 추가된 노래를 추가할 수 있는 경우는 1, 2이다. 3은 하나의 다른 곡이, 4는 2개의 다른 곡이 추가로 틀어진 뒤에야 가능하다.

따라서 만들어지는 배열은 [1, 2, 3, 4, 1], [1, 2, 3, 4, 2] 2개이다.

이는 이미 만들어져 있던 배열 수(1) * 이미 틀린 곡 중 추가할 수 있는 노래 수(4(i) - 2(K) = 2) = 2 이다.

이를 반대로 생각해보면 점화식을 다음과 같이 세울 수 있다.

dp[i][j] = dp[i-1][j-1] * (N - (j-1)) + dp[i][j-1] * (i - K)

정답은 dp[N][L]이 된다.

시간 복잡도는 O(NL).

---

소스코드 : https://gist.github.com/fpdjsns/be0f98d94ff503cc0cb8274128a34baa