BOJ 2305 자리 배치

먼저, 자유석을 기준으로 왼쪽 영역과 오른쪽 영역에 속하는 사람들의 배치는 독립임을 관찰합니다. 단, 한쪽 영역에서 빈 자리가 발생하면 남은 사람이 자유석을 차지해야 하므로, 양쪽 모두에서 빈 자리가 발생한 경우는 답에서 제외해야 합니다.

이제 한쪽 영역을 사람들이 꽉 채워 앉는 경우의 수와, 한 자리를 비우고 앉는 경우의 수를 DP로 다음과 같이 구할 수 있습니다.

• DP[n][a][b][c]: 첫 $n$명 중에서 $a$명을 빼고 배치하는 방법 중에서, $n$번째 자리에 $b$명이 앉고 $n+1$번째 자리에 $c$명이 앉는 방법의 수 ($0 \le n \le 40$, $0 \le a, b, c \le 1$)

초기조건은 다음과 같이 둡니다.

• DP[0][0][1][0] = 1 (아무도 배치하지 않은 경우, 0번째 자리는 채워져 있고 1번째 자리는 비어 있는 것으로 볼 수 있음)
• DP[0][a][b][c] = 0

그리고 전이는 다음과 같이 할 수 있습니다.

• DP[n+1][a][c][1] += DP[n][a][0][c] ($n$번째 자리가 비어있을 경우, $n+1$번째 사람을 $n$번 자리에 배치할 수 있음)
• DP[n+1][a][0][1] += DP[n][a][b][0] ($n+1$번째 자리가 비어있을 경우, $n+1$번째 사람을 $n+1$번 자리에 배치할 수 있음)
• DP[n+1][a][c][0] += DP[n][a][b][c] ($n+2$번째 자리는 항상 비어있으므로, $n+1$번째 사람을 $n+2$번 자리에 배치할 수 있음)
• DP[n+1][1][c][1] += DP[n][0][b][c] (지금까지 모든 사람을 배치했다면, $n+1$번째 사람을 스킵할 수 있음)

이제 길이 $n$의 영역을 꽉 채워 앉는 방법의 수는 DP[n][0][0][1]이고, 그 영역에서 한 자리를 비우는 방법의 수는 DP[n][1][0][1] + DP[n][1][1][1]이 됩니다. 이를 이용하여 정답을 구해서 출력하면 됩니다.