[백준 2302번] 극장 좌석 - (python)

문제 : https://www.acmicpc.net/problem/2302

 

 

 

Idea

고정좌석을 기준으로 배열을 나누고 각 나눠진 배열들에서 자리를 옮기는 경우는 독립적으로 일어나기 때문에 각각의 경우의 수를 구해서 곱하면 된다.

그러면 쪼개진 배열에서 자리를 바꿀 수 있는 경우의 수를 구하는 방법만 알면 된다.

 

만약 쪼개진 배열의 크기가 4라고 하면 [1,2,3,4] 총 4자리가 있다고 볼 수 있다. 이때 자리를 바꿔 앉을 수 있는 경우의 수를 구해야 되는데 그 경우의 수를 구하는 패턴을 찾기 위해 배열의 크기가 1 일때부터 그려봤다.

1일때는 그냥 1번 사람이 1번 좌석에 앉는 경우 1가지가 있다.

2일때는 1,2번이 자기 자리에 앉는 경우와 둘이 자리를 바꿔앉는 경우 2가지가 있다.

3일때는 1,2,3    2,1,3    1,3,2 총 3가지가 있다. 

근데 사실 3일때는 2일때 자리 배치에 뒤에 3을 추가한 것과 같다고 볼 수 있다. 그리고 추가로 3과 2가 자리를 바꾸는 경우가 추가된 것이다.

4일때는 3일때 자리 배치 뒤에 4를 추가한것과 4와 3이 자리를 바꾸는 경우가 추가되었다.

 

따라서 이전 값들이 계속 새로운 값을 구하는데 쓰이고 있기 때문에 값을 저장하기 위해 d라는 배열을 만들어 주었다.

 

d[i] : i 자리까지 존재할때 자리를 배치할 수 있는 경우의 수 

 

d[5]는 우선 d[4] 의 경우에 뒤에 5를 추가한 경우의 수 를 더하고 5와 4의 자리를 바꾸는 경우의 수를 더해야 하는데, 바로 앞에 4가 와야 가능하다. 바로 앞에 4가 오는 경우는 d[3] 의 개수와 같다. 왜냐면 d[3]의 경우에가 뒤에 4만 붙여주면 되기 때문.

따라서 점화식을 세우면 d[n]  = d[n-1] + d[n-2] 라는 점화식을 세울 수 있다.

 

 

 

코드

N = int(input())
M = int(input())

seat = [0]*(N) # 실제 좌석 번호는 0 ~ N-1 이라고 두고 품
vip = []
for _ in range(M):
    vip.append(int(input())-1) # 나중에 헷갈리지 않기위해 실제 좌석 번호 -1 로 입력

result = 1


def dp(n): #
    d = [0] * (n + 1)
    if n==1 or n==2:
        return n
    d[1] = 1
    d[2] = 2

    for i in range(3,n+1):
        d[i] = d[i-1] + d[i-2]

    return d[n]


# 고정좌석을 기준으로 배열을 쪼갠다.
s = 0
for v in vip:
    arr = seat[s:v]
    s = v + 1 # 배열 시작 위치 (인덱스)

    if len(arr)>0:
        result *= dp(len(arr))


arr = seat[s:]
if len(arr) > 0:
    result *= dp(len(arr))
print(result)