재밌는(?) 응용 dp문제이다.

먼저 우리는 남은 파이 개수, 가장 마지막으로 가져간 파이 개수가 최적해에 영향을 미친다는 것을 알 수 있다.

이를 통해 정의한다.

dp[i][j][k] = i명의 사람, j개의 파이가 남아있고 가장 마지막으로 가져간 파이 개수가 k일때 최적해

나는 탑다운 방식으로만 풀었는데, 다음엔 바텀업으로 해봐야겠다…

#include <bits/stdc++.h>
#define MEM 305
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
int n,k;
int dp[MEM][MEM][MEM];
int DP(int x, int y, int z) {
    int& ret=dp[x][y][z];
    if(ret) return ret;
    if(x==1 || x==y)
        return ret=1;
    for(int i=z; i*x<=y; i++)
        ret += DP(x-1,y-i,i);
    return ret;
}
main()
{
    sanic;
    cin >> n >> k;
    cout << DP(k,n,1);
}

---