문제 설명
2302번 극장 좌석과 비슷하게 본인의 좌석 번호와 인접한 (왼쪽, 오른쪽) 좌석에는 앉을 수 있지만 고정석이 사라지고 자유석이 추가된 문제입니다.
풀이
극장 좌석과 비슷한 문제라서 처음부터 DP로 접근하였습니다.
자유석을 기준으로 반으로 나눈 뒤 각각 경우의 수를 곱하면 답이 되지 않을까 해서 먼저 자유석이 존재하지 않은 경우부터 DP로 구하였습니다.
자유석이 존재하지 않는 좌석 n 개의 경우의 수를 fibo[n]에 저장하겠습니다.
fibo라고 배열 이름은 정한 이유는 다음을 보시면 아시겠지만 DP 점화식이 피보나치수열과 일치하기 때문입니다.
좌석이 4개인 경우의 수를 구하려고 합니다.
좌석 번호가 4인 사람은 두 가지 방법으로 좌석에 앉을 수 있습니다.
4번 좌석에 앉을 때와 왼쪽인 3번 좌석에 앉을 때입니다. 좌석의 끝이므로 오른쪽에는 앉을 수가 없습니다.
4번 좌석에 앉을 경우의 수는 좌석이 3개인 경우의 수에서 끝에 좌석 하나만 추가하면 되므로 fibo[3]입니다.
3번 좌석에 앉을 경우에는 3번 좌석 번호를 가진 사람은 2번, 4번 중에 한곳을 가야 하는데 2번을 가게 되면 1,2번 좌석 번호를 가진 사람은 4번 좌석에 앉지 못하기 때문에 3번 좌석 번호를 가진 사람은 4번 자리에 무조건 가야 합니다.
그러므로 3번 좌석에 앉을 경우는 fibo[2]입니다.
fibo[n] = fibo[n-1] + fibo[n-2]의 점화식이 됩니다.
이제 자유석을 포함한 경우의 수를 구해보겠습니다.
자유석이 여기저기 있을 경우에는 경우의 수를 구하기 힘들기 때문에 자유석이 가장 왼쪽에 있을 때 경우의 수를 구하겠습니다.
자유석을 포함한 좌석 n 개의 경우의 수를 dp[n]에 저장하겠습니다. dp[n]을 구하기 위해서는
-
n 번 사람이 n 번 자리에 앉았을 때
-
n 번 사람이 n-1 번 자리에 앉고 n-1 번 사람이 n 번 자리에 앉았을 때
-
n 번 사람이 자유석에 앉았을 때
-
n 번 사람이 n-1 번 자리에 앉고 n 번 자리가 공석일 때
로 경우를 나눠서 생각하겠습니다.
1번과 2번은 위에 구하는 방법과 동일하므로 어렵지 않게 구할 수 있습니다.
먼저 3번을 보겠습니다. n이 6일 때로 그림으로 보여드리겠습니다.
위 그림과 같이 공석의 위치에 따라 경우의 수가 다릅니다.
공석이 6번인 경우에는 2,3,4,5번 좌석은 알아서 앉을 수 있는 자리에 앉으면 됩니다.
그리고 이 경우의 수는 위에 자유석이 없는 좌석의 경우의 수와 동일하므로 그 값을 그대로 쓰면 됩니다.
공석이 5번인 경우는 6번 자리를 갈 사람이 5번 좌석번호를 가진 사람밖에 없기 때문에 그 사람이 앉아야 하고 2,3,4번 좌석은 알아서 앉으면 됩니다.
이런 식으로 공석의 위치에 따라 경우의 수를 구해주시면 되는데 식으로는
fibo[0] + fibo[1] + ··· + fibo[n - 3] + fibo[n - 2]입니다.
4번 n 번 사람이 n-1 번 자리에 앉고 n 번 자리가 공석일 때를 구하는 방법을 알아보겠습니다.
위에 1,2,3번을 하면 웬만한 건 다 구했을 거라 생각했지만 답이 나오지 않았습니다… ㅠ
모든 경우를 써보면서 구해보니 이 경우가 빠져있었습니다.
자유석에 2번 좌석 사람이 앉은 경우부터 보겠습니다.
나머지 3,4,5,6번 사람은 공석이 끝에 있기 때문에 한 칸씩 왼쪽으로 가서 앉을 수밖에 없습니다.
3번 사람이 자유석에 있는 경우는 4,5,6번 사람이 왼쪽으로 한 칸씩 가서 앉아야 하고,
4번 사람이 자유석에 있는 경우에도 5,6번 사람이 왼쪽으로 한 칸씩 가서 앉고 나머지 2,3번은 알아서 앉으면 됩니다.
이런 식으로 경우의 수를 구하게 되면
fibo[0] + fibo[1] + ··· + fibo[n - 4] + fibo[n - 3]라는 식이 나오게 됩니다.
fibo_sum[n]이라는 배열에 fibo_sum[n] = fibo[0] + fibo[1] + ··· + fibo[n]을 미리 저장하겠습니다.
이렇게 dp 식을 구하면
dp[n] = 1번 + 2번 + 3번 + 4번 = dp[n-1] + dp[n-2] + fibo_sum[n - 2] + fibo_sum[n - 3]입니다.
fibo_sum[n - 2] + fibo_sum[n - 3]은 아래처럼 fibo[1] + fibo[2] + ··· + fibo[n - 1]으로도 나타낼 수 있습니다.
자리 배치를 할 수 있는 모든 경우의 수는 자유석 k 기준으로 반을 나누었을 때
왼쪽에 자유석이 있을 경우 * 오른쪽에 자유석 없는 경우 + 왼쪽에 자유석이 없는 경우 * 오른쪽에 자유석이 있는 경우 - 왼쪽, 오른쪽 둘 다 자유석에 없는 경우
= dp[n - k + 1] * fibo[k - 1] + dp[k] * fibo[n - k] - fibo[k - 1] * fibo[n - k]
시간 복잡도는 O(n)입니다.
소스 코드
#include <cstdio>
int fibo[45], fibo_sum[45], dp[45], n, k;
int main() {
scanf("%d %d", &n, &k);
fibo[0] = fibo[1] = fibo_sum[0] = 1;
fibo_sum[1] = 2;
for (int i = 2; i <= n; i++) {
fibo[i] = fibo[i - 1] + fibo[i - 2];
fibo_sum[i] = fibo_sum[i - 1] + fibo[i];
}
dp[0] = dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2] + fibo_sum[i - 2] + fibo_sum[i - 3];
printf("%d\n", dp[n - k + 1] * fibo[k - 1] + dp[k] * fibo[n - k] - fibo[k - 1] * fibo[n - k]);
return 0;
}