BOJ) 12872 - 플레이리스트

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

12872번: 플레이리스트

길이가 p인 플레이리스트를 만드는 경우의 수를 구하는 다이나믹 프로그래밍 문제입니다.

X는 현재까지 플레이 리스트에 담긴 곡의 수, Y는 아직 플레이 리스트에 담기지 않은 곡의 수로,

X+Y는 항상 N이기에 메모리제이션에는 현재 플레이리스트의 길이 p와 담은 곡의 수 x만 사용하였습니다.

---

C++ 소스 코드

#include <cstdio>
#include <cstring>
#define MOD 1000000007
using namespace std;
long long d[101][101];
int n,m,p;
long long go(int idx,int x){
    int y = n-x;
    if (idx ==p){
        // 길이가 p인 리스트를 만들었을  때,
        // 추가하지 않은 곡이 0개라면 OK (모든 곡을  1번 이상 들어야함)
        if (y==0) return 1;
        else return 0;
    }
    long long &ret = d[idx][x];
    if (ret != -1) return ret;
    ret = 0;
    if (y>0) {
        // 아직 한 번도 추가 안한 곡이 y개 있다면
        ret+=go(idx+1,x+1)*y;
    }
    if (x > m) {
        // 추가된 곡의 수가 중복된 곡을 추가할 수 있는 최소 간격 이상일 때
        ret+=go(idx+1,x)*(x-m);
    }
    ret%=MOD;
    return ret;
}
int main(){
    scanf("%d %d %d", &n, &m, &p);
    memset(d,-1,sizeof(d));
    printf("%lld\n", go(0,0));
    return 0;
}