[백준 12872] 플레이리스트, C++

https://www.acmicpc.net/problem/12872

12872번: 플레이리스트

본 문제는 수빈이가 플레이리스트를 만들수 있는 경우의 수를 출력하는 문제다.

1. 모든 노래를 플레이리스트에 추가해야 하며
2. 노래를 중복해서 추가할 수 있다.
3. 하지만 중복된 노래를 추가 하려면, 두 곡 사이에 m개 이상의 곡이 있어야 한다.

#include <cstdio>
#include <cstring>
 
using namespace std;
 
long long d[101][101];
int n, m, p;
 
// len : 플레이리스트 길이
// pick : 노래를 선택한 개수
long long cal(int len, int pick) {
 
    // sur : 선택하지 않은 곡의 수
    int sur = n - pick;
 
    // 플레이리스트 길이가 수빈이가 들으려고 하는 곡 수 일 때
    if (len == p) {
 
        // 선택하지 않은 곡이 없을 경우
        if (sur == 0) return 1;
 
        // 선택하지 않은 곡이 있을 경우 제외
        else return 0;
    }
 
    auto &chk = d[len][pick];
    if (chk != -1) return chk;
 
    chk = 0;
 
    // 아직 선택하지 않은 곡이 있을 경우
    if (sur > 0) chk += cal(len+1, pick+1)*sur;
 
    // 선택한 곡이 m개를 넘을 경우
    // 이전에 선택한 곡을 추가해도 된다.
    if (pick > m) chk += cal(len+1, pick)*(pick-m);
 
    chk %= 1000000007;
 
    return chk;
}
 
int main () {
    scanf("%d %d %d", &n, &m, &p);
 
    memset(d, -1, sizeof(d));
    printf("%lld\n", cal(0, 0));
}