Q2302. 극장 좌석

연속된 일반석의 개수가 n개일때의 값을 dp로 구하는 로직

연속된 일반석이 n개일 경우의 가능수

k(n) = k(n-1) + k(n-2)

또한, 지정석은 정렬된 순서대로 알려주기 때문에,

end - start -1 로 연속된 일반석의 개수를 알 수 있습니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2302 { static boolean[] array; static int[] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int num = Integer.parseInt(st.nextToken()); array = new boolean[num+1]; dp = new int[41]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= num; i++) { dp[i] = dp[i-1] + dp[i-2]; } st = new StringTokenizer(br.readLine()); long result = 1; int fixedNum = Integer.parseInt(st.nextToken()); int startNum = 0; for (int i = 1; i <= fixedNum; i++) { st = new StringTokenizer(br.readLine()); int endNum = Integer.parseInt(st.nextToken()); int tempNum = endNum - startNum - 1; if (tempNum >= 2) { result *= dp[tempNum]; } startNum = endNum; } int endNum = num+1; int tempNum = endNum - startNum - 1; if (tempNum >= 2) { result *= dp[tempNum]; } System.out.println(result); } }