[BOJ/python] 2302: 극장 좌석

문제

✔️ silver 1

문제 흐름

경우의 수 문제는 오랜만인 느낌이었다.

이 문제의 패턴은 n=4까지 살펴보면 쉽게 파악할 수 있다.
패턴을 파악한 부분에서 이 문제는 DP임을 알 수 있다.

일단 memo는 2 x n 배열로 선언했는데, memo[i][0]은 i번째 좌석에 본인이 앉는 경우 앉을 수 있는 방법의 수, memo[i][1]은 본인이 앉지 않는 경우 앉을 수 있는 방법의 수로 정의했다.

사실 i번째 자리에 본인이 앉지 않는다면 남는 방법은 그전 사람과 바꿔앉는 방법 뿐이다.
이렇게 4까지 살펴보면서 패턴을 확인할 수 있는데,
바로 memo[i][0]은 앞의 모든 경우의 수가 되기 때문에 memo[i-1][0] + memo[i-1][1]이 되고,
memo[i][1]은 앞에서 본인이 앉은 경우에만 이전 사람과 바꿔 앉을 수 있기 때문에 memo[i-1][0]가 된다.

여기서 이제 이 문제에서의 하나의 제한사항을 체크해준다.
바로 VIP인데, 여기는 자리를 바꿔앉아주지 않는다. ^^
이는 4번 좌석이 vip인 경우 n이 4, 5인 경우를 통해 패턴을 확인 가능하다.

i가 vip인 경우 당연히 그 자리에 본인밖에 앉을 수 없으므로 이전 경우의 수 모두가 memo[i][0]이 되어 memo[i-1][0] + memo[i-1][1]이 되고, memo[i][1]은 자연스럽게도 0이 된다.
근데 이게 vip 다음 자리에도 마찬가지다.
본인 자리에 본인이 앉지 않는 방법은 앞사람과 바꿔 앉는 방법 뿐인데 앞사람이 바꿔주지않기 때문에 똑같이 넘어오게 된다.
j를 vip 자리를 저장한 리스트의 인덱스로 사용하여
vip 다음 자리까지 memo를 계산하고나면 j를 하나 증가시켜 다음 vip석을 확인할 수 있도록 했다.

코드

# 극장 좌석

import sys
input = sys.stdin.readline

def dp (n: int, lst: list):
    # memo[i][0]: i번째 좌석까지 앉을 때 i번째 자리에 본인이 앉는 경우 앉을 수 있는 방법 가짓수
    # memo[i][1]: i번째 좌석까지 앉을 때 i번째 자리에 본인이 앉지 않는 경우 앉을 수 있는 방법 가짓수
    memo = [[0, 0] for i in range(n)]
    memo[0] = [1, 0]

    j = 0 # lst의 idx
    for i in range(1, n):
        if j < len(lst):
            if i == lst[j]:
                memo[i] = [sum(memo[i - 1]), 0]
                continue
            elif i == lst[j] + 1:
                memo[i] = [sum(memo[i - 1]), 0]
                j += 1
                continue
        memo[i] = [sum(memo[i - 1]), memo[i - 1][0]]
    
    # print(* memo)
    return sum(memo[-1])

if __name__ == "__main__":
    n = int(input())
    m = int(input())
    
    vip = []
    for i in range(m):
        num = int(input()) - 1
        vip.append(num)
    
    result = dp(n, vip)
    print(result)