백준 2303번 극장 좌석 (JAVA)

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

2302번: 극장 좌석

 

저는 다음 문제를 DP를 이용하여 문제를 해결하였습니다.

저는 좌석을 뒷 사람만 하고 변경 가능하다고 문제를 재해석하였습니다.

(2번,1번 좌석 변경 == 1번,2번 좌석 변경)

그래서 현재 좌석과 다음 좌석이 VIP인지 판별하고 VIP라면 좌석 변경이 불가능하기 때문에

DP[depth] = DP[depth+1]로 하였습니다.

만약 VIP가 아니라면 현재 좌석을 변경가능하기 때문에

DP[depth] = DP[depth+1] + DP[depth+2]로 하였습니다.

(depth+1은 좌석을 변경하지 않았을 때의 경우의 수, depth+2는 좌석을 변경한 경우의 수입니다.)

 

 

재귀

package BOJ.DP;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.function.Function;

public class BOJ_2303 {

    private static int dfs(int depth, boolean[] isVip, int n,int[] dp) {
        if (depth > n) {
            return 0;
        }
        if (depth == n) {
            return 1;
        }
        if(dp[depth] != 0){
            return dp[depth];
        }
        int result = 1;
        if (isVip[depth] || (depth +1 < n && isVip[depth + 1])) {
            result = dfs(depth + 1, isVip, n,dp);
        } else {
            result = dfs(depth + 1, isVip, n,dp) + dfs(depth + 2, isVip, n,dp);
        }
        dp[depth] = result;
        return result;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String, Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        int m = stoi.apply(br.readLine());
        boolean[] isVip = new boolean[n];
        for (int i = 0; i < m; i++) {
            int num = stoi.apply(br.readLine()) - 1;
            isVip[num] = true;
        }
        int[] dp = new int[n];
        System.out.println(dfs(0, isVip, n,dp));
    }

}

 

for문

package BOJ.DP;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.function.Function;

public class BOJ_2303 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        int m = stoi.apply(br.readLine());
        boolean[] isVip = new boolean[n];
        for(int i = 0 ; i < m ; i++){
            int num = stoi.apply(br.readLine()) - 1;
            isVip[num] = true;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        if(isVip[1] || isVip[0]){
            dp[1] = 1;
        }else{
            dp[1] = 2;
        }
        for(int i = 2 ; i < n ; i++){
            if(isVip[i] || isVip[i-1]){
                dp[i] = dp[i-1];
            }else{
                dp[i] = dp[i-2] + dp[i-1];
            }
        }
        System.out.println(dp[n-1]);
    }
}