[백준 2302 : JAVA] 극장 좌석 / DP

문제

---

 

 

 

풀이

---

점화식을 찾을 수 있는지 묻는 문제이다.

가장 먼저 노가다로 좌석이 4개일 때까지의 경우의 수를 구해보자. (DP에서 점화식을 찾을 때 3~4 정도까지는 노가다로 그려보자)

좌석이 1개일 때)

1

 

좌석이 2개일 때)

1 2

2 1

 

좌석이 3개일 때)

1 2 3

1 3 2

2 1 3

 

좌석이 4개일 때)

1 2 3 4

1 2 4 3

2 1 3 4

2 1 4 3

1 3 2 4

 

노가다로도 쉽게 구할 수 있는 4개까지 구해보니, [1, 2, 3, 5] 라는 수열을 얻을 수 있었다. 

DP[i] = DP[i - 1] + DP[i - 2] 인가... (가장 흔한 피보나치 수열 점화식) 대충 어림짐작해보고 좌석이 5일 경우로 넘어가보자.

 

좌석이 5개쯤부터는 노가다로 힘들어진다. 이 구간에서는 DP의 철학대로 한 번 쪼개서 생각해보자.

 

[그림 1] 좌석 5개를 4개 + 1개로 나눠본 모습

 

위 경우처럼 쪼개서 구한 경우의 수와 중복되지 않을 경우는 어떤 경우일까?

마지막 5번 좌석이 앞으로 가는 경우다.

 

[그림 2] 좌석 5개를 3개 + 2개로 나눠본 모습

 

더 이상 쪼개는건 무의미하다. 경우의 수에 중복이 발생할 것이기 때문이다.

따라서, 점화식 DP[i] = DP[i - 1] + DP[i - 2] 를 구했다.

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    private static int N, M;
    private static int[] cache;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        cache = new int[N + 1];
        cache[0] = 1;
        cache[1] = 1;
        cache[2] = 2;
        for (int i = 3; i <= N; i++) {
            cache[i] = cache[i - 1] + cache[i - 2];
        }

        int result = 1, prev = 0;
        for (int i = 0; i < M; i++) {
            int temp = Integer.parseInt(br.readLine());
            result *= cache[temp - prev - 1];
            prev = temp;
        }
        result *= cache[N - prev]; // 마지막 vip 좌석 다음 좌석에서 끝 좌석까지의 경우의 수.

        System.out.println(result);
    }
}