[알고리즘] 백준 - 극장좌석

문제

극장 좌석

 

풀이

- 이 문제는 고정석을 기준으로 풀어야 한다

- 시작점 - 고정석 - 고정석 - 끝점 : 사이의 3칸을 기준으로 사이사이에 몇칸이 있는지 확인하고 새로운 배열에 넣어둔다

- 새롭게 넣어둔 배열의 원소 값들로 피보나치 수열 이랑 같은 점화식으로 결과값 이끌어 내면서 값들을 곱하면 된다

 

코드

# 실버 1 - 2302
import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

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

    for i in range(m):
        data = int(input())
        d[data-1] = 0

    res = []
    cnt = 0
    for i in range(n):
        if d[i] != 0:
            cnt += 1
            if i == n-1:
                res.append(cnt)
        else:
            res.append(cnt)
            cnt = 0

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

    ans = 1
    for i in res:
        ans *= dp[i]
    print(ans)
else:
    for _ in range(m):
        v = int(input())
    print(1)