규칙을 찾기 위해 먼저 그려봤다!
그런데 같은 M 내에서도 VIP 석의 번호에 따라서 경우의 수가 달라지니,,, 그걸 다 따지는 것이란 불가능해보였다.
그러다가 문제를 다시 읽어봤는데, 웬 걸 그림을 보고 생각이 났다!
(아마도 힌트를 주기 위해서 그림을 의도적으로 문제에 표시한 거 아닐까??!🫠)
VIP석은 항상 고정석이기 때문에 VIP석을 기준으로 양옆으로 구획이 나뉜다!!
그러니까 전체를 N개로 생각하지말고, VIP석 기준 왼쪽 따로 오른쪽 따로 구해서 모두 곱하면 되는 것이다!!
그러니까 이렇게 된다는 것이다
그렇다면 위와 같을 때의 경우의 수는 이렇다!
그리고 DP 배열은 정의는 이렇다!
그럼 이제 DP 배열만 완성시킬 수 있으면 정답을 구할 수 있는 것이다.
몇 가지만 적어보면 금방 규칙을 찾을 것이다!
보면 dp[i]를 구하려고 하면,
1. 이전 케이스인 dp[i-1]의 케이스들의 뒤에 i를 붙인 것과
2. i가 i-1번 좌석에 앉은 케이스
이렇게 두 가지로 나눠서 생각할 수 있다.
전자는 정확히 dp[i-1]만큼 발생한다.
후자는 i가 i-1에 앉으면, i-1은 i에 앉아야 한다.
그렇다면 그 앞의 1부터 i-2까지의 좌석의 경우의 수만 생각하면 되는데,
그건 이미 앞에서 구해놓은 dp[i-2]다!
그렇기에 점화식은 이렇게 된다!
이제 이것을 식으로 옮겨적으면 정답이 될 것이다!!
정답
주의할 점이 있다!
나 같은 경우는 DP배열을 N+1개 생성했다.
그렇게 해야 나중에 각 구획의 경우의 수를 곱할 때 편하기 때문이다.
그리고 그렇게 했을 때, VIP석이 이어져있다면, DP[0]을 곱하게 되는데 이 부분을 1로 초기화 해놓지 않으면 중간에 0이 곱해져서 답이 0으로 나올 수 있다!
이걸 고치지 않아서 한 번 틀렸다🤣
조심하자!!
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// N, M 입력 받기
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
// DP
int[] dp = new int[N + 1];
dp[0] = 1; // 안 하면 VIP석이 연속으로 있을 때 답이 0 나옴!
dp[1] = 1;
if (N >= 2) dp[2] = 2;
for (int i = 3; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
// VIP석 입력 받기
int ans = 1, before = 0, vip;
for (int i = 0; i < M; i++) {
vip = Integer.parseInt(br.readLine());
ans *= dp[vip - before - 1];
before = vip;
}
ans *= dp[N - before];
System.out.println(ans);
}
}