[BOJ] 1309

동물원

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

“전체를 부분으로 빈틈없이 쪼개는 최적의 기준을 만들자” 라는 교훈을 얻은 문제였습니다.

cage[i] 를 구한다고 할 때,
첫 번째 줄이 처음으로 사자가 들어와있지 않은 줄인 경우는 cage[i - 1]
두 번째 줄이 처음으로 사자가 들어와있지 않은 줄인 경우는 2 × cage[i - 2]
세 번째 줄이 처음으로 사자가 들어와있지 않은 줄인 경우는 2 × cage[i - 3]
…
i번째 줄이 처음으로 사자가 들어와있지 않은 줄인 경우는 2 × cage[0]
모든 줄에 사자가 들어와있는 경우는 2 임을 이용하여
cage[i] = cage[i - 1] + 2 × (cage[i - 2] + cage[i - 3] + … + cage[0]) + 2 의 점화식을 만들면 됩니다.

2 × (cage[i - 2] + cage[i - 3] + … + cage[0]) 을 미리 저장해두고 이용하지 않으면 시간초과가 납니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1309.cpp