[백준/2302] 극장 좌석 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버1
출처 : 백준 - 극장 좌석

🦧 문제 풀이 접근

VIP좌석을 제외하고 붙어있는 각각의 자리에서 가능한 모든 경우의 수를 곱하면 된다.
DP를 통해 각각 붙어있는 좌석에서의 경우의 수를 계산할 수 있다.

예시)
좌석이 2인 경우 -> [1,2], [2,1]
좌석이 3인 경우 -> [1,2,3], [1,3,2], [2,1,3]

이때 좌석이 4인 경우는 마지막 좌석이 4인경우와 마지막 좌석이 3인 경우의 합이다. 즉
[1,2,3,(4)], [2,1,3,(4)], [1,3,2,(4)] -> 3
[1,2,(4,3)], [2,1,(3,4)] -> 2
-> 3+2 = 5
위 식을 통해 점화식을 유추하면 f(n) = f(n-1) + f(n-2)
즉 피보나치 수열의 형태를 띈다.

위 점화식을 바탕으로 DP 배열에 값은 넣고 답을 구할 수 있다.

💻 code

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int answer=1;
        int nArr[] = new int[M+2];
        nArr[0] = 0;
        nArr[M+1] = N+1;
        for(int i=0;i<M;i++) {
            nArr[i+1] = Integer.parseInt(br.readLine());
        }
        int DP[] = new int[41];
        DP[0]=1;
        DP[1]=1;
        DP[2]=2;
        for(int i=3;i<41;i++) {
            DP[i] = DP[i-2]+DP[i-1];
        }
        for(int i=1;i<=M+1;i++) {
            answer*=DP[nArr[i]-nArr[i-1]-1];
        }
        System.out.println(answer);
    }
}

🥇 결과

🎓 느낀점

DP문제 답게 점화식만 찾으면 쉽게 문제를 해결 할 수 있을 줄 알았으나, VIP 좌석이 붙어있는 경우 값이 0이 나와버리는 오류를 못찾아서 시간이 조금 걸렸다.