[BOJ] 2253번: 점프

https://www.acmicpc.net/problem/2253

D[i][j]를 직전에 j칸 점프해서 i번째 돌에 도달하기 위한 최소 횟수라고 할 때, D[i][j]는 min(D[i-j][j-1], D[i-j][j], D[i-j][j+1], D[i-j+1][j-2], D[i-j+1][j-1], D[i-j+1][j], D[i-j-1][j+2], D[i-j-1][j+1], D[i-j+1][j])+1로 구할 수 있습니다. i는 최대 N이고 j는 j*(j+1)/2 <= N인 최대의 j이므로 대략 sqrt(N) 정도이기에 O(N*sqrt(N))에 구할 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/2253.cpp