[Python/파이썬] 백준 2302번 극장 좌석

2302번: 극장 좌석

 

문제

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

입력

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

출력

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < $2^{31}-1$)

코드

n = int(input())
fixed = []
for _ in range(int(input())):
    fixed.append(int(input())) 

dp = [1] * 41       # 좌석이 n개일 때 가능한 좌석 배치의 수(VIP 고려 X)
dp[2] = 2
dp[3] = 3

for i in range(4, 41):
    dp[i] = dp[i-2] + dp[i-1]

prev = 0
ans = 1
if fixed:
    for f in fixed: # VIP
        ans *= dp[f-prev-1]
        prev = f
    ans *= dp[n-prev]  # 마지막 부분 좌석 처리
else:
    ans = dp[n]
print(ans)

 

dp배열에는 좌석의 수가 i개일 가능한 좌석 배치의 수가 저장된다. 

 

좌석의 개수가 3개일 때까지는 경우의 수가 적어서 쉽게 구할 수 있다.

그 이후부터는 점화식을 이용하여 구할 수 있는데 다음과 같다.

$$dp[i] = dp[i-2] + dp[i-1]$$

예를 들어 자리가 4개일 때를 살펴보면 4번이 본인 번호에 앉는 경우와 본인 번호가 아닌 곳에 앉는 경우 2가지로 나눌 수 있다.

즉, dp[i]에는 티켓 번호와 동일한 자리에 앉는 경우(dp[i-1])와 자신의 티켓 번호보다 1개 앞의 번호에 앉는 경우(dp[i-2])를 더한 겂이 저장된다.

 

이제 dp에 저장된 값들을 이용하여 문제를 풀면 된다.

VIP는 자리를 바꿀 수 없으므로 VIP를 기준으로 구역을 나눠서 각 경우의 수들을 구하여 곱해주면 된다.

 

 

 

처음에는 DP로 풀 생각을 하지 못하고 백트래킹+비트마스킹을 이용하여 풀이하려했다.

n = int(input())
m = int(input())
fixed = set()
for _ in range(m):
    fixed.add(int(input())) 

ans = 0

def dfs(idx, seat):
    global ans
    if idx == n:
        ans += 1
        return
    # VIP석
    if idx+1 in fixed:
        if (1<<idx) & seat != 0:   # 고정좌석을 누가 이미 선점
            return
        else:
            seat |= (1<<idx)
    else:
        for i in [-1, 0, 1]:
            if 0 <= idx+i < n:
                if (1<<idx+i) & seat != 0:  # 이미 누가 앉아있는 자리
                    return
                else:
                    dfs(idx+1, seat|(1<<idx+i))
dfs(0, 0)
print(ans)

사람이 이미 앉아있는 경우를 1, 앉아있지 않은 경우를 0으로 하여 0 ~ N-1번 자리까지 고정좌석에 VIP가 앉으려 했는데 누가 이미 앉아있는 경우, N번 티켓으로 N-1, N, N+1번 모두 앉을 수 없는 경우를 가지치기하여 해결하려 했으나 실패하여 위 코드와 같이 DP를 이용하여 풀었다.