https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp[n+1][3] dp[n][0] -> n행의 0열은 n행에 아무것도 넣지 않았을때를 뜻함 dp[n][1] -> n행의 1열은 1번째 열에 사자를 넣을 경우의 수를 뜻함 dp[n][2] -> n행의 2열은 2번째 열에 사자를 넣을 경우의 수를 뜻함 따라서 점화식은 dp[n][0] = dp[n-1][0] + dp[n-1][1]+ dp[n-1][2] : 아무것도 넣지 않았을 경우에는 다른 열의 영향이 없기 떄문에 이전 행의 모든 경우의 수를 합한 값이 된다. dp[n][1] = dp[n-1][0]+dp[n-1][2] : 1번째 열에..