문제 링크

문제 해설

Idea

  • Dynamic Programming
  • 자리를 옮길 수 있는 연속되는 좌석의 수는 피보나치 수열을 따름 (S[i] = F[i+1])
  • VIP 좌석 번호를 기준으로 연속되는 좌석의 수를 리스트로 저장
  • 모든 연속되는 좌석 수에 대한 피보나치 수를 곱하고 출력

Sequence

S2 (1,2) -> (1,2), (2,1) = 2(F3)
S3 (1,2,3) -> (1,2,3), (2,1,3), (1,3,2) = 3(F4)
S4 (1,2,3,4) -> (1,2,3,4), (2,1,3,4), (1,2,4,3), (1,3,2,4), (2,1,4,3) = 5(F5)
S5 (1,2,3,4,5) -> (1,2,3,4,5), (1,2,4,3,5), (1,2,3,5,4), (2,1,3,4,5), (2,1,4,3,5), (2,1,3,5,4), (1,3,2,4,5), (1,3,2,5,4) = 8(F6)
S6 (1,2,3,4,5,6) -> (1,2,3,4,5,6), (1,2,4,3,5,6), (1,2,3,5,4,6), (1,2,3,4,6,5), (1,2,4,3,6,5), …

Time Complexity

  • DP: O(N) = 40

Data Size

  • N: 1 <= int <= 40
  • M: 0 <= int <= N
  • answer: int < 2^31-1

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())

seats, idx = list(), 0
for _ in range(M):
    vip = int(input())
    seats.append(vip-idx-1)
    idx = vip
seats.append(N-idx)

F = {1:1, 2:1}
def fibonacci(n):
    if n in F:
        return F[n]
    F[n] = fibonacci(n-1) + fibonacci(n-2)
    return F[n]

answer = 1
for seat in seats:
    if seat > 1:
        answer *= fibonacci(seat+1)

print(answer)