백준1309

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp 는 3 * (n+1)의 공간으로 만들어 주었다. 사자를 배치하는 것에 대해 생각해보면 다음과 같은 세 가지 이다. 1. 사자를 배치하지 않는 경우 dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] 2. 사자를 왼쪽 칸에 배치하는 경우 사자를 연속해서 왼쪽 칸에 배치할 수 없으므로, 이전 계산 값 (dp[i-1])에서 오른쪽에 배치한 경우와 배치하지 않는 경우의 수를 가져온다. dp[i][1] = dp[i-1][0] + dp[i-1][2] 3. 사자를 오른 쪽 칸에 배치하는 경우 사자를 연속..