[BOJ/JAVA] 2302번: 극장 좌석

2302번: 극장 좌석

문제 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.

https://www.acmicpc.net/problem/2302

키워드

• 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.

• 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.

• “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

• 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력

---

구현

VIP 회원들은 자기 좌석에만 앉아야 하므로, 배열의 해당 인덱스에 넣어 두고 시작한다.

일반 회원의 자리바꾸기의 경우의 수

• 내 왼쪽으로 가기

• 내 오른쪽으로 가기

• 3명의 일반회원이 서로 섞이는 경우는 없다.

static int cache[]

[i]인덱스 부터 시작할 때 사람들이 좌석에 앉을 수 있는 방법의 가짓수

static int dp(int index)

현재 인덱스토부터 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 반환

1. 마지막 인덱스에 도달했다면.. 종료 (1가지 경우의 수 이므로)
   • 1 반환

2. cache[index] 의 값이 -1이 아니라면
   • cache[index] 반환

3. 현재 자리를 바꾸지 않는 경우
   • 단순히 index를 1 증가
   • cache[index] += dp(index + 1)

4. 현재 자리를 바꾸는 경우
   • VIP가 아니여야 바꿀 수 있음
     • 인덱스를 2 증가
     • cache[index] += dp(index + 2)

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class java_2302 {
    // 좌석의 개수
    static int N;
    // 고정석(VIP)의 개수
    static int M;

    // [i]번째 인덱스부터 시작할 때
    static int cache[];

    static boolean seats[];

    // 현재 인덱스부터 사람들이 좌석에 앉을 수 있는 방법의 가짓수
    static int dp(int index) {
        // 마지막 인덱스 까지 도달했다면..종료
        if (index >= N) {
            return 1;
        }

        // 이미 값이 존재한다면..
        if (cache[index] != -1) {
            return cache[index];
        }

        // 현재 값이 VIP 라면?
        if (seats[index]) {
            return dp(index + 1);
        }

        cache[index] = 0;

        // 바꾸지 않는 경우
        cache[index] += dp(index + 1);
        // [i,i+1] 바꾸는 경우
        // 다음 인덱스가 존재해야하며, VIP가 아니여야 함
        if (index + 1 < N) {
            if (!seats[index + 1]) {
                cache[index] += dp(index + 2);
            }
        }

        return cache[index];
    }

    static int solution() {
        // 캐시 초기화
        cache = new int[N];
        Arrays.fill(cache, -1);

        int result = dp(0);

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        seats = new boolean[N];
        for (int i = 0; i < M; i++) {
            int vip = Integer.parseInt(br.readLine());
            seats[vip - 1] = true;
        }

        int result = solution();

        System.out.println(result);

        br.close();
    }
}

---

Uploaded by N2T