Array Challenge

풀이

정신 나갈것 같은 문제. 감도 안잡히는 복잡한 점화식이 주어진다..
태그를 까보면 벌리캠프-매시를 돌려야 한다는 것을 알수 있긴 하지만, 태그없이는 대체 제곱근에 floor까지 붙은 형태의 함수가 선형 점화식 꼴로 표현될수 있을거라는 상상을 어떻게 할수 있을지..
아무튼 벌리캠프-매시를 돌려보면 정말 충격적이게도 이 복잡한 형태의 점화식이 인접 3항간의 선형점화식으로 표현된다. 너무 간단해서 어이가 없을지경..
실제 제출 코드에는 이렇게 구한 점화식의 계수를 그냥 적어놓고, 입력으로 들어오는 n에 대해 n번째 항의 값을 O(logn)에 계산해주면 끝.

(다이아몬드 이상은 코드 생략)