nodeal dev story

solved.ac 실버 5에 랭크되어 있지만 재미있는 문제다. 어지간히 복잡한 방법을 사용해서 해결하더라도 수열의 길이가 1,000을 넘지 않는다는 점에서 해결이 어려운 문제는 아니다. 하지만 상수 시간에 해결할 수 있다면 어떨까? 문제에서 주어진 수열은 다음과 같다: \(a_n\) = 1 2 2 3 3 3 4 4 4 4 5 5 5 ... 1이 1번, 2가 2번, 3이 3번, 4가 4번 나오는 방법이 반복되는 것이다. 이때 수열 \(a_n\)의 \(n\)번째 항까지의 합을 \(S(n)\)라고 하자. 문제에서 입력 A와 B가 주어질 때 A부터 B번째 수까지의 합은 다음과 같이 표현할 수 있다. $$S(B) - S(A) + a_A$$ 그렇다면 \(S(n)\)와 A번째 항 \(a_A\)를 상수 시간에 구할 수..