BOJ 2303 재풀이

DP로 푼다.

내꺼 기준 왼쪽만 본다.

 

- 내가 왼쪽이랑 숫자를 바꾸려 하면 : 왼쪽 숫자는 변경되지 않은 상태일때만 가능

- 내가 왼쪽이랑 숫자를 바뀌지 않는다면 : 왼쪽 숫자가 변경되었든 아니든 상관 없음.

 

근데 내 왼쪽이 vip거나 내가 vip 면 그냥 왼쪽의 모든 방법을 더해주면 된다.

 

즉, 앞의 상태를 가지고 있는 DP

 

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean[] seat = new boolean[n+1];
        int vips = sc.nextInt();
        
        for(int i=0; i<vips; i++) {
            seat[sc.nextInt()] = true;
        }
        
        int[][] dp = new int[2][n+1];
        
        dp[0][1] = 1;
        
        // 0 -> 지금 숫자는 바뀐게 아닐때
        // 1 -> 지금 숫자가 바뀐거일때
        
        for(int i=2; i<=n; i++) {
        // 앞이나 내가 vip 면 그냥 가면 됨
            if(seat[i] || seat[i-1]) dp[0][i] = dp[0][i-1] + dp[1][i-1];
            else {
                dp[0][i] = dp[1][i-1] + dp[0][i-1]; // 안바꿔줄거면 앞이 바뀌었든 안바뀌었든 다 올수 있음
                dp[1][i] = dp[0][i-1]; // 바꿔줄거면 앞이 안바뀐 상태일때만 가능
            }
        }
        
        System.out.println(dp[0][n] + dp[1][n]);
    }
}