[BOJ 24516] 백준 24516번 - 잘 알려진 수열 구하기
1. 문제
$24516$. 잘 알려진 수열 구하기 (2022 ICPC Sinchon Winter Algorithm Camp Contest H번)
백준 24516번 - 잘 알려진 수열 구하기 (https://www.acmicpc.net/problem/24516)
2. 풀이
우연히 정답일 것 같은 수열을 찾았고, 이를 제출했더니 맞았다. 인접한 두 수가 $2$로 나누어지게 하고, 세 수가 $3$으로 나누어지게 하고… 이렇게 계속 만들다보니 그럴싸한 정답이 나온 것이다.
여러 시행착오를 통해 공차가 $2$인 등차수열이 문제의 조건을 만족함을 알게 되었다. 정답을 도출하는 명확한 방법은 모르겠다. 그러나 정답 수열을 정의하고 나서 증명은 가능했다. 이 등차수열의 $x$항부터 $y$항까지의 합을 수식으로 정리해보았다.
\[\begin{aligned} \displaystyle\sum_{k=x}^{y}{a+2k} &=a(y-x+1)+2\times(\frac{y(y+1)}{2}-\frac{x(x-1)}{2})\\ &=a(y-x+1)+y^2-x^2+y+x\\ &=a(y-x+1)+(y-x)(y+x)+(y+x)\\ &=a(y-x+1)+(y+x)(y-x+1)\\ &=(y-x+1)(a+y+x) \end{aligned}\\\]$x$항부터 $y$항까지의 합이므로 길이는 $(y-x+1)$이다. 위 식에서 볼 수 있듯이 합은 길이로 나누어진다. 따라서 공차가 $2$인 등차수열은 문제의 조건을 만족하는 수열임을 알 수 있다.
3. 채점 결과
4. 회고
.
댓글남기기