[BOJ] Q2302 극장 좌석

[BOJ] Q2302 극장 좌석

Question

Language: Python

Difficulty: Silver 1

해당 문제는 vip 자리는 고정으로 정해두고, 나머지 자리를 배치하는 경우만 제대로 파악하면 된다. 또한, vip를 중간에 벽으로 생각하고 나머지 부분에 대한 경우는 다 제각각으로 배치하는 것이므로, 독립사건이라고 볼 수 있다. 따라서, vip를 경계로 각각의 배치에 대한 곱으로 생각할 수 있다.

즉, 아래와 같은 예시가 있을때,

1 2 3 4 5 6 7 8 9

위의 자리 배치 경우는 1 2 3 배치하는 경우 * 5 6 배치하는 경우 * 8 9 배치하는 경우로 표현할 수 있다.

또한 vip가 아닌 사람에 대해 배치하는 경우는 아래와 같은 점화식을 가지는 것을 확일할 수 있다.

n=1 일때 1 n=2 일때 12,21 n=3 일때 123,213,132 n=4 일때 1234,1324,2134,1243,2143이다

n=3일때를 분석해보면 123 213 132

n=4인 경우는 1234 2134 1324 1243 2143

자세히 보면 di[i]=di[i-1]+di[i-2]임을 확인할 수 있다.

Solution

def solution():
    di=[0] * 41
    di[0]=1

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

    start=1
    result=1
    for vip in vips:
        result*=di[vip-start]
        start=vip+1

    result*=di[n_seats-start+1]

    return result

if __name__ == "__main__":
    vips=[]
    n_seats=int(input())
    n_vips=int(input())
    for _ in range(n_vips):
        vips.append(int(input().strip()))
        
    print(solution())