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

D[i]를 2*i 크기의 동물원에 사자를 배치하는 경우의 수라고 할 때,

최초로 사자가 들어있지 않은 행이 0행인 경우 : D[i-1]

최초로 사자가 들어있지 않은 행이 1행인 경우 : 2*D[i-2]

최초로 사자가 들어있지 않은 행이 2행인 경우 : 2*D[i-3]

.

.

최초로 사자가 들어있지 않은 행이 i행인 경우 : 2*D[0]

모든 행에 사자가 들어있는 경우 : 2

이므로 D[i] = D[i - 1] + 2 * (D[i-2]+D[i-3]+...+D[0]) + 2가 됩니다. 이 때 D[0]~D[j]까지의 합을 저장하고 매번 구할 때 마다 D[i-1]을 추가하는 식으로 진행하면 O(n)만에 계산할 수 있습니다.(그렇지 않을 경우 O(n^2)이 되어 시간 초과가 발생할 것입니다.)

https://github.com/encrypted-def/BOJ/blob/master/1309.cpp