백준 1309. 동물원

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

1309번: 동물원

 

사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다.

이 문장을 잘못 해석해서 가로 세로 동시에 있지만 않으면 된다는 뜻으로 알고 한참 해맸다.

가로에도 있으면 안되고 and 세로에도 있으면 안된다는 뜻이다.

 

각 행에 사자가 없는경우, 왼쪽에만 있는 경우, 오른쪽에만 있는 경우로 나눠서 푼다.

d[n][0] : 세로 길이 n이고, n번 행에 사자가 없는 경우 

d[n][1]: 세로 길이 n이고, n번 행에 왼쪽(0열)에만 사자가 있는 경우 

d[n][2]: 세로 길이 n이고, n번 행에 오른쪽(1열)에만 사자가 있는 경우 

 

bottom-up