음악 플레이어에 서로 다른 N곡의 노래가 저장되어 있고, 여행 중 L곡을 듣고 싶다고 가정해 봅시다. 이때 다음 조건을 만족하는 플레이리스트를 만들어야 합니다.
- 모든 노래는 최소 한 번 이상 재생되어야 합니다.
- 어떤 노래를 다시 재생하려면, 그 전에 반드시 K개의 다른 노래가 먼저 재생되어야 합니다.
우리가 구해야 할 것은 가능한 플레이리스트의 총 개수입니다. 답이 매우 커질 수 있으므로, 결과는 10^9 + 7로 나눈 나머지를 반환합니다.
예를 들어 입력이 N = 2, L = 3, K = 0이라면 출력은 6입니다. [1,1,2], [1,2,1], [2,1,1], [2,2,1], [2,1,2], [1,2,2]와 같이 총 6가지의 플레이리스트가 존재하기 때문입니다.
문제 해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있습니다. dp[i][j]를 "i곡을 재생했고, 그중 서로 다른 노래가 j종류인 경우의 플레이리스트 수"로 정의합니다.
핵심 아이디어
- i번째 위치에서 새로운 노래를 추가하는 경우: 남은 새 노래는 (N - (j - 1))개이므로, dp[i-1][j-1] * (N - (j - 1))을 더합니다.
- i번째 위치에서 이미 들었던 노래를 다시 재생하는 경우: j > K일 때만 가능하며, 재사용 가능한 노래는 j - K개이므로 dp[i-1][j] * (j - K)를 더합니다.
알고리즘 단계
- 모듈러 연산을 위한 add(), sub(), mul() 함수를 정의합니다.
- add(a, b): ((a mod m) + (b mod m)) mod m 반환
- sub(a, b): ((a mod m) - (b mod m) + m) mod m 반환
- mul(a, b): ((a mod m) * (b mod m)) mod m 반환 - 크기가 (L + 1) × (N + 1)인 2차원 배열 dp를 생성하고, dp[0][0] := 1로 초기화합니다.
- i를 1부터 L까지 순회하면서, 각 i에 대해 j를 1부터 N까지 순회하며 다음을 수행합니다.
- dp[i][j] := mul(dp[i - 1][j - 1], (N - (j - 1)))
- 만약 j > K라면, dp[i][j] := add(dp[i][j], mul(dp[i - 1][j], j - K))를 수행합니다. - 최종적으로 dp[L][N]을 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
typedef long long int lli;
class Solution {
public:
int add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
int sub(lli a, lli b){
return ((a % m) - (b % m) + m) % m;
}
int mul(lli a, lli b){
return ((a % m) * (b % m)) % m;
}
int numMusicPlaylists(int N, int L, int K) {
vector < vector <int> > dp(L + 1, vector <int>(N + 1));
dp[0][0] = 1;
for(int i = 1; i <= L; i++){
for(int j = 1; j <= N; j++){
dp[i][j] = mul(dp[i - 1][j - 1], (N - (j - 1)));
if(j > K){
dp[i][j] = add(dp[i][j], mul(dp[i - 1][j], j - K));
}
}
}
return dp[L][N];
}
};
main(){
Solution ob;
cout << (ob.numMusicPlaylists(2, 3, 0));
}입력
2,3,0
출력
6
이 알고리즘의 시간 복잡도는 O(L × N)이며, 공간 복잡도 역시 O(L × N)입니다. 두 개의 중첩 반복문으로 DP 테이블을 채워나가기 때문에 입력 크기가 커져도 효율적으로 동작합니다.