f(n, k) =

for i = 0 to n-1

f(n-1, k-i)

라는 것 까지는 도출했는데 역시나 시간초과가 나서 공식답안을 봤더니

f(n, k) = f(n, k-1) + f(n-1, k) – f(n-1, k-n)

이라는 식으로 유도를 하더군요.

이 부분이 생각을 해봐도 왜 이런건지 잘 모르겠습니다. ㅠㅠ