어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.
그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.
오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.
예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.
맞다. 피보나치 수열과 동일하다. 각각의 구간의 경우의 수를 구했으므로, 전체 구간의 경우의 수는 그 모든 경우의 수의 곱이 된다.
init : 초기화 함수. VIP를 입력받아, VIP마다 일반 좌석 구간을 계산하여 리스트에 저장한다.
make_dp : 앞선 점화식에 따라 DP 리스트를 계산하여 작성한다. 일반 좌석 구간 리스트(movable_list)의 최댓값까지 계산하면 된다. DP 리스트를 반환한다.
calculate : DP 리스트를 전달받아, 일반 좌석 구간 리스트의 경우의 수의 곱을 계산하여 반환한다.
solve : 메인함수. init 함수의 호출로 movable_list를 작성하고, make_dp를 통하여 계산된 dp를 calculate 함수에 전달하여 최종 계산값을 출력한다.
풀이 코드
N = int(input())
M = int(input())
movable_list = list()
def init() :
if M == 0 :
movable_list.append(N)
return
prev = 1
for _ in range(M) :
now = int(input())
if now - prev :
movable_list.append(now - prev)
prev = now + 1
if now != N :
movable_list.append(N - prev + 1)
def make_dp() :
if not movable_list :
return list()
max_val = max(movable_list)
dp = [0]*(max_val+1)
dp[0] = dp[1] = 1
for i in range(2, max_val+1) :
dp[i] = dp[i-1] + dp[i-2]
return dp
def calculate(dp) :
result = 1
for mv in movable_list :
result *= dp[mv]
return result
def solve() :
init()
dp = make_dp()
result = calculate(dp)
print(result)
solve()
