와 진짜 맞네요. 혹시 어떻게 점화식을 구했는지 알려주실 수 있나요?

기억은 안 나지만, 수식 정리를 했을거에요.

만약에 항이 무수이 많은 꼴인 형태의 문제였으면(아님 말고요 ㅎ) 인자에 n을 넣은 경우랑 우변에 처음으로 나오는(아마 n-1 또는 n-2) 번호를 넣은 경우 이 두 가지에 대한 식을 빼주면 뒤에 많은 항들을 잘라줄 수 있습니다.

혹은 적당한 규칙성으로 확인했을 수도 있을 듯 한데 제가 원래 점화식이 기억이 안 나요ㅠ

원래 점화식이 이차원 배열인데 이걸 어떻게 저렇게 간결하게 만들 수 있을지 모르겠네여..

dp[n,1] = dp[n-1,1];

dp[n,2] = dp[n-2,1] + dp[n-2,2];

dp[n,3] = dp[n-3,1] + dp[n-3,2] + dp[n-3,3];

주신 점화식에 따르면, 합을 새로운 항 S_n으로 치환하고 양 변을 모두 더해서 식을 간결하게 바꿀 수 있을 겁니다.

dp[n,1] + dp[n,2] + dp[n,3] = dp[n-1,1] + dp[n-2,1] + dp[n-2,2] + dp[n-3,1] + dp[n-3,2] + dp[n-3,3]

S_n = S_n-3 + dp[n-1,1] + dp[n-2,1] + dp[n-2,2]

S_n = S_n-3 + dp[n-1,1] + dp[n-2,1] + dp[n-2,2]

S_n = S_n-3 + k + dp[n-2,2]

dp[n-2,2]를 n에 관한 값으로 바꾸면 비슷할 것 같습니다.

마지막에 dp[n-2,2]를 바꾸려고 해도 안 됐지만 그래도 많은 것을 알게 됐습니다. 감사합니다!

방금 글에 좋아요를 누가 눌러주셔서 봤는데 제가 잘못 적은 것 같네요.

$dp(n,k):=n$을 $1\cdots k$를 이용해서 구성하는 방법의 수

정도로 정의가 된 것으로 보이네요.

따라서 $dp(n,3)$이 답이고, $dp(n,3)=dp(n-1,1)+dp(n-2,2)+dp(n-3,3)$이 되는데,

$dp(n-1,1)$은 자명히 $1$이고, $dp(n-2,2)$는 $\lfloor (n-2)/2\rfloor + 1$이므로 다 더하면 결국

$dp(n,3)=dp(n-3,3)+\lfloor n/2\rfloor +1$이됩니다.

방금 또 누가 좋아요를 눌러주셔서 봤는데 이거 일반항도 구할 수 있어요.
$a_n=a_{n-3}+\lfloor n/2 \rfloor + 1\ (n> 3);\ a_1=1, a_2=2, a_3=3$
약간 바꿔서
$a_n=a_{n-6}+n\ (n \ge 6);\ a_0=a_1=1,a_2=2,a_3=3,a_4=4,a_5=5$로 표현할 수 있어요.
$6$으로 나눈 나머지에 따라 각 초항은 조금씩 달라지지만 큰 틀에서 등차수열을 띠므로...이차식으로 합을 대체할 수 있습니다.
$\alpha n^2+\beta n+\gamma-(\alpha(n-6)^2+\beta (n-6)+\gamma)=n$
$\frac 1 {12} n^2 +\frac 12n+\gamma$
$\gamma$는 초항에 좌지우지되는 값입니다.
통분해서 $\frac {n(n+6)+\gamma'} {12}$라고 표현할 수 있겠죠.
$n\mod 6 = 0\to \gamma' = 12$
$n\mod 6 = 1\to \gamma' = 5$
$n\mod 6 = 2\to \gamma' = 8$
$n\mod 6 = 3\to \gamma' = 9$
$n\mod 6 = 4\to \gamma' = 8$
$n\mod 6 = 5\to \gamma' = 5$
근데 나눗셈에서 내림을 고려하면 그냥 $\gamma'$을 $12$로 고정해도 문제가 없다는 걸 알 수 있습니다.
따라서 `(n*(n+6)+12)/12`를 출력해주면 됩니다.