[2302] 극장 좌석

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

풀이방법

• 만약 5개의 좌석의 배치를고민할때,
  1+4, 2+3과 같이 나누어서 결정할 수 있다.
  따라서 dp[n] = dp[n-1]+ dp[n-2]

import sys

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    arr = []

    dp = [-1 for _ in range(N + 2)]
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2


    def sol(length):
        if dp[length] != -1:
            return dp[length]

        dp[length] = sol(length - 1) + sol(length - 2)

        return dp[length]

    for i in range(3, N + 1):
        sol(i)
        
    if M == 0:
        print(dp[N])

    else:
        prev = 0
        answer = 1
        for _ in range(M):
            x = int(sys.stdin.readline())
            answer *= dp[x - prev - 1]
            prev = x
        answer *= dp[N - prev]
        
        print(answer)