[BOJ] 2302번: 극장 좌석

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

이 문제를 풀 때 쓰이는 중요한 성질은 2가지입니다.

1. VIP 좌석을 일종의 칸막이로 여기고, 분리된 좌석들끼리 배치할 수 있는 경우의 수를 곱하면 됩니다. 문제의 예시로 설명하자면 전체 경우의 수 = 1-3번 좌석을 배치하는 경우의 수 * 5-6번 좌석을 배치하는 경우의 수 * 8-9번 좌석을 배치하는 경우의 수로 구할 수 있습니다.

2. N명이 연속해있는 좌석에 사람들을 앉히는 경우의 수는 F_n(피보나치 수)입니다.

2번 성질은 D[i] : VIP석 없이 1~i을 배치할 경우의 수

D[N]을 구하기 위해 N번 학생이 어디에 앉는지로 케이스를 나눠봅시다.

Case 1 - N번 학생이 N번 자리에 앉는 경우 : 1~N-1번 학생들을 잘 앉히면 되므로 D[N-1]

Case 2 - N번 학생이 N-1번 자리에 앉는 경우 : N-1번 학생은 반드시 N번 자리에 앉아야하고, 나머지 1~N-2번 학생들을 잘 앉히면 되므로 D[N-2]

그러므로 D[N] = D[N-1]+D[N-2]가 되고, 초기항 D[1] = 1, D[2] = 2이기 때문에 피보나치 수가 됩니다.

이 두 성질만 이끌어내고 나면 구현 자체는 쉽습니다.

https://github.com/encrypted-def/BOJ/blob/master/2302.cpp