[Baekjoon] DP - 2302 극장 좌석

문제

2302번: 극장 좌석

 

풀이

1. 극장 좌석은 최대 40개의 의자를 놓을 수 있으므로 40개가 들어갈 수 있는 배열을 초기화한다.

2. d[n]은 극장 좌석이 n개일 때, 자리에 앉을 수 있는 경우의 수다.

  2-1. n자리가 될 때, 자리를 바꾸지 않는 경우 (맨 오른쪽에 앉게 됨)

  2-2. n자리가 될 때, 자리를 바꿔 않는 경우 (맨 오른쪽에서 두번째에 앉게 됨)

  2-3. 즉, d[n] = d[n - 1] + d[n - 2]가 극장 좌석이 n자리 일 때, 자리에 앉을 수 있는 경우의 수가 된다.

3. 각 자리마다 vip는 제자리에 앉아야하므로, vip 전후에 앉을 수 있는 의자의 개수를 구한다.

4. 앉을 수 있는 의자의 수만큼 자리에 앉을 수 있는 경우의 수가 달라진다.

   4-1. 6개의 의자가  있는 경우, vip가 4번 자리에 앉을 때 => (1~3(3개)와 5~6(2개)은 자리를 바꿔가며 앉을 수 있다.)

5. vip를 기준으로 남은 좌석으로 앉을 수 있는 경우의 수를 구한 후 곱한다.

 

from functools import reduce


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

d = [0] * 41


def solution(n, vips, d):
    result = []

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

    for vip in vips:
        result.append(d[vip - current_vip - 1])
        current_vip = vip

    if current_vip < n:
        result.append(d[n - current_vip])

    return reduce(lambda x, y: x * y, result)


print(solution(n, vips, d))

 

채점 결과