그냥 F(n) = F(n - 1) + F(n - m) 하면 되는데요 ㅠㅠ. 질문자 님의 식은 제가 이해를 못 하겠어서 이 식으로 설명을 드리면 편의상 F(0) = 1, n<0이면 F(n) = 0으로 정의하고 다음과 같은 식을 세웁니다.
(F(n + m) F(n + m - 1) ... F(n + 2) F(n + 1))T = A (F(n + m - 1) F(n + m - 2) ... F(n + 1) F(n))T
이때 A가 m * m짜리 행렬이 되야겠죠. 그러면 A의 2행부터 m행까지는 해당되는 자리의 F(...)를 고르면 되고 1행은 F(n + m - 1) + F(n)을 하면 되니까 A가 대략
1 0 0 0 0...... 1
1 0 0 0 0 0 0 0..
0 1 0 0 0 0 0...
0 0 1 0 0 0 0...
...
0 0 0 0 0 0 0 1 0
이렇게 되는 거예요.
ktjooho 4년 전
질문 게시판에서 검색해본결과 점화식을 세워, 행렬식으로 유도해 dp 로 푼다는 힌트를 참고했습니다.
찾아낸 점화식이 맞았는지 먼저 확인하고 싶습니다.
m = b의 스킬 시간.
i = index
F(m*i) = 2 * F(m*(i-1)) + F(m*(i-2) + 1) + F(m*(i-2) + 2) + .... + F(m*(i-1) -1 )
라는 점화식이 나옵니다.
b 의 스킬 시간의 배수를 중심으로 항상 길이가 b 의 스킬시간크기 m 만큼 나오는 식인데요.
b 의 스킬 시간 배수에 해당되는 조합의 갯수는 구하고자하는 배수보다 하나 작은 크기의 이전 조합크기의 2배에 이전 조합보다 하나 작은
시간 크기에서 스킬 크기 m - 1 개의 조합 갯수를 더하면 현재 m*i 에 대한 크기를 구할 수 있다는 식입니다.
여기서 행렬 m by m 을 어떻게 만들어야될지 감이 안 옵니다.
혹시 점화식이 틀렸으면 어떤점이 틀렸는지 알려주시면 감사하겠습니다.