[JAVA] 백준 (실버1) 2302번 극장 좌석

링크

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

---

입력 예제

9
2
4
7

---

출력 예제

12

---

풀이

고정석을 제외한, 좌석 이동이 가능한 경우의 수를 구해야 한다. 좌석은 좌우로 밖에 이동할 수 없기 때문에 고정석을 기준으로 독립적이라 할 수 있다. 따라서 연속적인 좌석을 기준으로 생각해봐야 하기 때문에 dp배열을 다음과 같이 정의한다.

dp[i]: 연속된 자리의 개수가 i개일 때 앉을 수 있는 경우의 수

연속된 좌석이 1개일 경우는 어짜피 이동할 수 없으므로 dp[1] = 1이 된다. 입장권 번호가 1일 때, {1}가 된다.

연속된 좌석이 2개일 경우는 입장권 번호가 1, 2일 때, {1, 2}, {2, 1}가 되며 dp[2] = 2가 된다.

연속된 좌석이 3개일 경우는 입장권 번호가 1, 2, 3일 때, {1, 2, 3}, {2, 1, 3}, {1, 3, 2}가 되며 dp[3] = 3이 된다. 이 경우를 생각해보면 마지막 좌석에서 이동했을 경우와 이동하지 않았을 경우로 나눌 수 있다. 이동했을 경우는 {1, 3, 2}, 이동하지 않았을 경우는 {1, 2, 3}, {2, 1, 3}인데 3을 기준으로 앞 좌석을 생각해보면 각각 연속된 좌석이 1개와 2개일 경우가 된다. 따라서 dp[3] = dp[2] + dp[1]이 된다.

연속된 좌석이 4개일 경우는 {1, 2, 3, 4}, {2, 1, 3, 4}, {1, 3, 2, 4}, {1, 2, 4, 3}, {2, 1, 4, 3}이 된다. 이 역시 마지막 좌석인 4의 이동 여부로 생각해보면 이동하지 않았을 때는 연속된 좌석이 3개일 때의 경우의 수가 되고, 이동했을 때는 연속된 좌석이 2개일 때의 경우의 수가 된다. 즉, dp[4] = dp[3] + dp[2]가 되며 이를 일반화하면 dp[n] = dp[n-1] + dp[n-2], 피보나치 수열 수열이 된다.

이를 코드로 구현하면 다음과 같다.

int[] dp = new int[41];
dp[0] = 1;  //모두 고정석일 때 역시 이동할 수 없음
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= N; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];  //피보나치 수열
}

이제 연속된 좌석에 대한 경우의 수를 구했으니 고정석을 기준으로 각 연속된 좌석의 개수를 구하고, 각 사건은 독립적으로 발생하므로 각 경우를 곱해주면 된다.

int answer = 1;
for (int i = 1; i < seats.size(); i++) {
    //고정석 사이 거리
    int gap = seats.get(i) - seats.get(i - 1) - 1;
    answer *= dp[gap];
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        List<Integer> seats = new ArrayList<>();  //고정석 번호
        seats.add(0);  //0번 고정석으로 취급
        for (int i = 0; i < M; i++) {
            seats.add(Integer.parseInt(br.readLine()));
        }
        seats.add(N + 1);  //N+1번 고정석으로 취급

        //dp[i]: 연속된 자리의 개수가 i개일 때 앉을 수 있는 경우의 수
        int[] dp = new int[41];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        int answer = 1;
        for (int i = 1; i < seats.size(); i++) {
            //고정석 사이 거리
            int gap = seats.get(i) - seats.get(i - 1) - 1;
            answer *= dp[gap];
        }

        System.out.println(answer);
    }
}