[백준] 2302 극장 좌석 java

1. 문제 설명

문제 링크

뭔놈의 극장이 티켓을 샀는데, 양 옆으로 옮겨 앉을 수 있음...
예를 들어 3번 좌석을 산 사람은 4번 좌석에 앉아도 되고, 2번 좌석에 앉아도 됨.
하지만 3번 좌석을 산 사람이 양 옆 이외의 좌석에는 못 앉음. 예를 들어 7번 좌석이나 1번 좌석으로 이동은 불가.

또, VIP석이라는 개념이 있음. 이름이랑 맞지 않게 이거 산 사람은 그냥 그 자리 앉아야함.
예를 들어 7번 좌석이 VIP석이면 7번 산 사람은 7번에 무조건 앉아야함.

N번까지의 좌석이 있고, 만석일 때, 사람들끼리 자리를 바꿔 앉을 수 있는 경우의 수를 구하라.

2. 접근 방식

도저히 못 풀겠어서 다른 사람 풀이를 봤다.
KEY WORD : DP

(1) 기본 원리

패턴이 안 보이면, 무작정 가짓수를 적어서 패턴을 생각해봐야 한다는 것을 깨달았다. 해당 문제의 패턴은 다음과 같다.
(일단 고정석은 생각하지 말자.)

좌석이 1 개일 때, 앉을 수 있는 경우의 수는 1가지 이다.
좌석이 2개 일 때, 티켓 1번과 티켓 2번이 서로 자리를 바꿔 앉을 수 있다. (1,2), (2,1) 따라서 경우의 수는 2가지다.
좌석이 3개 일 때, (1,2,3), (1,3,2), (2,1,3)으로 3가지이다.
좌석이 4개 일 때, (1,2,3,4), (2,1,3,4), (1,3,2,4), (1,2,4,3),(2,1,4,3) 으로 5 가지 이다.
좌석이 5개 일 때, (1,2,3,4,5), (2,1,3,4,5), (1,3,2,4,5), (1,2,4,3,5), (1,2,3,5,4),(2,1,4,3,5),(2,1,3,5,4),(1,3,2,5,4)로 8가지이다.

피보나치 수열과 거의 유사한 형태임을 알 수 있다. 따라서 DP 점화식은
(i>2 일 때) dp[i] = dp[i-1] + dp[i-2]이다.

(2) 고정석을 산정해보자.

이건 쉽다. 고정석은 어짜피 고정 되어있어서 경우의 수를 만들지 못한다. 또한 양 옆의 자리만 바꿀 수 있으니,
고정석이 생기면, 고정석 이후부터 다시 피보나치 수열 시작이다.

따라서 풀 수 있는 방법은 2가지이다.

1. 위의 생각한 그대로 고정석 나올 때마다 dp 새로 세기
2. dp는 일단 N개에 관해서 전부 구해놓고, 고정석을 만날 때마다 가용 범위 만큼 구해서 쓰기

1번은 직관적이니까 넘어가고, 2번의 경우가 무엇을 뜻하는지 알아보자
일단 문제의 예시처럼 N=9라고 할때, dp를 다 구하면 다음과 같다.

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

4번이 고정석이라면 무슨 소리일까? 1~3번 3개의 자리에서만 자리를 바꾸는 경우의 수를 구하면 된다. 따라서 답은 3이다.
7번에서 고정석을 또 만나면 5,6번 자리 바꾸기만 생각하면 된다. 따라서 답은 2이다.
마지막도 8,9 두 자리를 바꾸면 되니까 답은 2이다.
각 자리를 바꾸는 경우는 동시에 일어나므로 곱해야 한다. 따라서 3x2x2 해서 정답은 12이다.

3. 코드 분석

1번 풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        int ans = 1;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int [] dp = new int[N+1];
        dp[0] = -1;
        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            int now = Integer.parseInt(br.readLine());
            dp[now] = -1;
        }
        for (int i = 1; i <= N; i++) {
            if(dp[i] == -1) continue;
            if(dp[i-1] == -1) {dp[i] = 1;}
            else if(dp[i-2] == -1) {dp[i] = 2;}
            else dp[i] = dp[i-1] + dp[i-2];

            if(i+1 > N || dp[i+1] == -1) ans *= dp[i];
        }
        System.out.println(ans);
    }
}

2번 풀이

import java.io.*;
import java.util.*;

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

        int N = Integer.parseInt(st.nextToken());
        if(N == 1) {
            System.out.println(1);
            return;
        }
        int [] dp = new int [N+1];
        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 ans = 1;
        int vip_recent = 0;
        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int vip_now = Integer.parseInt(st.nextToken());
            ans *= dp[vip_now - vip_recent-1];
            vip_recent = vip_now;
        }
        ans *= dp[N-vip_recent];
        System.out.println(ans);
    }
}

!! 왜 dp[0] = 0이 아니라 1 입니까?

원래 dp[0]는 사용하지 않는 배열 원소이다. 하지만 2번 풀이와 같이 풀면 쓸 때가 있다. 만약 고정석이 9개의 좌석 중 6번 7번에 연달아 있다고 해보자.
만약 7-6-1이므로 dp[0]를 사용해야 하는데, dp[0] = 0 이면 이후, 경우의 수로 뭘 구하든 답이 0이 나온다.
고정석이 연달아 있을 경우, 그 사이 좌석 배치 경우의 수는 딱 그 한가지 이므로 dp[0] = 1 로 해야지 경우의 수를 구하는데 차질이 없다.

4. 성장 하기

두 번째 풀이의 dp[0] = 0 이 아니라 1인 이유를 찾는데 시간이 많이 들었던 것 같다. 질문 게시판에 누군가 올린 질문을 통해 답을 알 수 있었다.