Number of Music Playlists(Math,Dynamic Programming,Combinatorics)

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

 

Your music player contains n different songs. You want to listen to goal songs (not necessarily different) during your trip. To avoid boredom, you will create a playlist so that:

• Every song is played at least once.
• A song can only be played again only if k other songs have been played.

Given n, goal, and k, return the number of possible playlists that you can create. Since the answer can be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 3, goal = 3, k = 1
Output: 6
Explanation: There are 6 possible playlists: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].

Example 2:

Input: n = 2, goal = 3, k = 0
Output: 6
Explanation: There are 6 possible playlists: [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], and [1, 2, 2].

Example 3:

Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].

 

Constraints:

• 0 <= k < n <= goal <= 100

또 징글징글한 Dynamic programming에 이번엔 Hard 난이도 문제지만, 한 번 부딪혀보자.

 

겁나리 어렵다.

 

원래 문제가 쉬워보여도 막상 풀이 들어가면 어려운 케이스가 많았는데,

 

이건 문제부터 어렵다.  진짜 쉽지 않다..

 

우야노 이걸

 

그냥 수학문제 같았는데, GG.. 이것도 DP로 푼다고 한다.

 

 

1.Python

 

쉽지 않은 접근법이었다.

코드는 간단해 보여도 저 곱하기 부분이 어렵다

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [[0]*(n+1) for _ in range(goal+1)]
    # dp[i][j] represent the number of playlists of length i that include exactly j unique songs.
        dp[0][0] = 1

        for i in range(1,goal+1):
            for j in range(1,n+1):
                # add a new song
                dp[i][j] += dp[i-1][j-1] * (n-(j-1))
                # Reuse an old song
                if j > k :
                    dp[i][j] += dp[i-1][j] * (j-k)
                # Take modulo
                dp[i][j] %= MOD
                
        return dp[goal][n]

 

2.C

#C
#include <stdio.h>
#define MOD 1000000007

int numMusicPlaylists(int n, int goal, int k) {
    // 동적 배열 생성
    long long dp[goal + 1][n + 1];
    for (int i = 0; i <= goal; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = 0;
        }
    }
    
    // 초기 값 설정
    dp[0][0] = 1;

    // DP 테이블 채우기
    for (int i = 1; i <= goal; i++) {
        for (int j = 1; j <= n; j++) {
            // 새로운 곡 추가
            dp[i][j] = dp[i - 1][j - 1] * (n - (j - 1)) % MOD;
            // 기존 곡 재사용
            if (j > k) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - k)) % MOD;
            }
        }
    }

    return dp[goal][n];
}

 

 

3.C++

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;

int numMusicPlaylists(int n, int goal, int k) {
    // 동적 배열 생성
    vector<vector<long long>> dp(goal + 1, vector<long long>(n + 1, 0));

    // 초기 값 설정
    dp[0][0] = 1;

    // DP 테이블 채우기
    for (int i = 1; i <= goal; i++) {
        for (int j = 1; j <= n; j++) {
            // 새로운 곡 추가
            dp[i][j] = dp[i - 1][j - 1] * (n - (j - 1)) % MOD;
            // 기존 곡 재사용
            if (j > k) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - k)) % MOD;
            }
        }
    }

    return dp[goal][n];
}