재밌는(?) 응용 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);
}
코딩공부 같이하고 싶은 사람은 백준의 "그룹입니다" 그룹에 신청해주세요.
https://www.acmicpc.net/group/6712
_DynamicCube