자연계열 3번

[문제 3-1] 첫째항을 $\displaystyle a$라 하면$\displaystyle am+\frac{m(m-1)}2\le N$이므로$\displaystyle 1\le a\le\frac Nm-\frac{m-1}2$이다.

$\displaystyle N=mq+r$, $\displaystyle 0\le r<m$이라 하면$\displaystyle m$이 홀수이므로가능한 $\displaystyle a$의 최댓값은 $\displaystyle q-\frac{m-1}2$이다.이 값이 $\displaystyle 1$보다 작으면 가능한 $\displaystyle a$는 없으므로$\displaystyle g_N(m)=\begin{cases}\frac{N-r}{m}-\frac{m-1}2&\left(\frac{N-r}{m}-\frac{m-1}2\ge1\right)\\0&\left(\frac{N-r}{m}-\frac{m-1}2<1\right)\end{cases}$이다.

[문제 3-2] 길이가 $\displaystyle m$인 수열 하나는 그 합 $\displaystyle N$에 대해 $\displaystyle f(N)$에 $\displaystyle m$만큼 기여한다.따라서 길이별로 모아 세면$\displaystyle \sum_{N=1}^{200}f(N)=\sum_{\substack{1\le m\le19\\m\text{은 홀수}}}m\,g_{200}(m)$이다.여기서 가장 작은 합이 $\displaystyle \frac{m(m+1)}2$이므로$\displaystyle \frac{m(m+1)}2\le200$을 만족하는 홀수는 $\displaystyle 1,3,\ldots,19$이다.

이 순서대로 $\displaystyle g_{200}(m)$을 구하면$\displaystyle 200,65,38,25,18,13,9,6,3,1$이므로$\displaystyle \begin{aligned}\sum_{N=1}^{200}f(N)&=200+3\cdot65+5\cdot38+7\cdot25+9\cdot18\\&\quad+11\cdot13+13\cdot9+15\cdot6+17\cdot3+19\\&=1342\end{aligned}$이다.