https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 알고리즘 분류 : DP 푸는 과정 사자의 배치는, 각 행별로 없거나 앞의 행의 대각선에만 배치가 가능하다. 앞이 00이라면, 00 10 01 이 가능 앞이 10이라면 00,01 앞이 01이라면 00,10 이 가능 하다. 말하자면, 2*N칸의 우리에 사자를 배치할 수 있는 경우의 수는 N번째칸에 00이 가능한 경우의 수 + 01이 가능한 경우의수 + 10이 가능한 경우의 수인데, 각 경우를 d[n][0] / d[n][1] / d[n][2] 이라고 하면 d[n][0] = d[n-1][0] + d[n-1][1] + d[n-1][2] d..