Sicily 1687 Permutation

어젯밤에 제목을 봤는데 DP인 것 같았는데 나중에 보니 어려워요.해냈어, 해냈어?
그래서 선생님께서 주신 문제풀이를 보고 간략하게 썼다.그러나 대체로 생각이 떠올랐다. 처음으로 3차원 DP를 사용했는데 신기했다.
그리고 내가 이 문제를 써야 한다고 생각했다.
오늘 오전에 오전의 반을 써서 잇따라 세 가지 방법을 바꾸어 마침내 해냈다.
========================================================
제목 대의: 원제는 영어로 말하기가 매우 까다롭다. 번역하면 1-N 개수의 서열에서 비교한다. 몇 가지 배열 방식으로 K개가 나타날 수 있느냐고 묻는다.
eg:1 3 5 4 2 can be changed to 1<3<5>4>2. 
문제 해결 방법:
dp[i][k][j]는 i개의 수가 있으면
초기화: dp[0][0][0] = 1;
상태 이동 방정식: dp[i][k][1] = dp[i-1][k][i-1]
    dp[i][k][j] = dp[i][k][j-1] + ( dp[i-1][k][i-1] - dp[i-1][k][j-1] + dp[i-1][k-1][j-1] )
참고 사항:
1. 제목 데이터는 매우 크지만 제목은 결과% 2007을 출력해야 하기 때문에 매번 dp[i][k][j]를 계산한 후에 dp[i][k][j]% 2007을 출력한다.
2. 1로 인해 또 다른 문제가 발생할 수 있다.'dp[i-1][k][i-1]-dp[i-1][k][j-1]'에서 마이너스가 나타날 경우 매번 얻은 dp[i][k][j]+2007*x를 dp[i][k][j]까지 정수로 한다.
3. 전체 3차원 그룹에 대한 해답을 밖에 두면 해답을 한 번만 할 수 있다.
코드:

#include
#include
#include
using namespace std;
int dp[105][105][105];

int main()
{
		dp[0][0][0] = 1;
		for(int i = 1 ; i <= 100 ; i++)
		{
			for(int k = 0; k < i ; k++)
			{	
				dp[i][k][1] = dp[i-1][k][i-1];
				for(int j = 2; j <= i ; j++)
				{
					dp[i][k][j] = dp[i][k][j-1] + dp[i-1][k][i-1] - dp[i-1][k][j-1];
					if(k>0) dp[i][k][j] += dp[i-1][k-1][j-1];
					if(dp[i][k][j] < 0) dp[i][k][j]+= 2007;
					if(dp[i][k][j] >= 2007) dp[i][k][j] %= 2007;
				}
			}
		}
	int n,k;
	while(scanf("%d%d" , &n , &k)!=EOF)
	{
		printf("%d
", dp[n][k][n]);
	}
}

==========================================================
가슴 아픈 과정:
처음에 dp의 상태를 i개수로 정의했는데 k개는 번호보다 작고 마지막 하나는 j로 4개의 for를 만들었는데 결과적으로 TLE가 되었다.
그리고 위에서 정의한 상태를 생각해낸 결과 WA가 나왔다. 그 이유는 dp[i][k][j-1]를 추가할 줄 몰랐기 때문이다.
그리고 푸린에게 물었더니 푸린은sum수조를 만들어서 저장하자고 제안했다.나는 사고방식이 매우 정확하다고 생각하지만 왜 정확한 결과를 얻지 못하는지 모르겠다. 아마도 상태 이동 방정식이 틀렸을 것이다.
나중에 나는 갑자기 나의 이전 방법이 쓸 수 있다는 것을 생각했다.
마지막으로 니가 본 이거.