문제

image.png

image.png

풀이

  • 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수 없다. (대각선으로만 배치 가능하다)
  • 1번째 줄에 1번째 칸에 사자가 들어가 있으면, 2번째 줄에는 2번째 칸에 사자가 들어가야 한다.
  1. n = 1 인 경우
00
01
10
  1. n = 2 인 경우
0 0
0 0
0 0
0 1
0 0
1 0
0 1
1 0
0 1
0 0 
1 0
0 1
1 0
0 0

dp[i][0] = dp[i-1][0] * 3
dp[i][1] = dp[i-1][1] * 2
dp[i][2] = dp[i-1][2] * 2