Dynamic Programming
문제
어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.
그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.
오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.
예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.
입력
첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.
출력
주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
fibo = [1, 1] + [0] * (N + 1) # 피보나치의 편의를 위해 [1, 1]을 앞에 껴주고 시작
VIP = [0]
gap = []
answer = 1
for i in range(2, len(fibo)): # 피보나치 수열 생성
fibo[i] = fibo[i - 1] + fibo[i - 2]
for i in range(M):
VIP.append(int(input())) # VIP석. 예시에선 4, 7
VIP.append(N + 1)
# VIP석을 통해서 일반석의 길이를 구하기 위해 양 끝의 값은 1과 (N + 1)로 박아둔다.
for i in range(1, len(VIP)):
gap.append(VIP[i] - VIP[i - 1] - 1)
# 연속된 일반석들의 길이를 구해준다.
for i in range(len(gap)):
answer *= fibo[gap[i]]
print(answer)
4와 7을 기준으로 유동적인 자리갯수가 연속되는 3개(1, 2, 3), 2개(5, 6), 2개(8, 9)이다. 각 부분마다 가능한 경우는 3개 => 3, 2 => 2개, 2 => 2개.
이것을 4개와 5개로 확장해보면 5, 8가지가 나온다. 즉
1, 2, 3, 5, ∙∙∙ N까지가 되는데 이 규칙은 피보나치 수열
fibo[i] = fibo[i - 1] + fibo[i - 2]의 점화식을 따른다.
따라서 연속된 부분들의 가능한 경우의 값들을 곱셈누적시킨다.
일반석을 0, VIP석을 1로 생각한다면
[0, 0, 0, 1, 0, 0, 1, 0, 0,]4번째 자리 전까지 0의 갯수는 3개, 7번째 전까지 2개, 7번째 이후 2개
즉 fibo[3 - 1] x fibo[2 - 1] x fibo[2 - 1] = 3 x 2 x 2 = 12.
다른 예시로 만약 총 9자리에 VIP석이 3번째 8번째라면 연속된 부분은 2, 4, 1
=> fibo[2 - 1] x fibo[4 - 1] * fibo[1 - 1] = 2 x 5 x 1 = 10
N이 반드시 9개로 주어지지 않을수도 있어서 이 과정을 피보나치 수열을 N의 크기에 맞게 일반화로 초기화 한다. 단 편의를 위해 [1, 1]을 처음부터 붙이고 시작한다.
