[백준] 2302 극장 좌석 - Dynamic Programming / Java

• 문제 링크

2302번: 극장 좌석

 

• 풀이 과정

vip석에 따라 점화식 구조가 달라지므로 각각의 vip석 번호를 Set 에 저장해둔다.

 

만약 vip석이 존재하지 않는 경우, n = 0 ~ 4 까지의 경우의 수를 구해 규칙성을 찾아내면

dp[i] = dp[i - 1] + dp[i - 2] 의 점화식을 구할 수 있다.

 

하지만 현재 또는 이전 좌석이 vip석일 경우, (set.contains(i) || set.contains(i - 1))

해당 좌석으로 자리 이동이 불가하므로 이전에 구해진 경우의 수에서 변경이 없다.

즉 dp[i] = dp[i - 1] 의 점화식이 성립하고 입력값이 Set에 저장된 vip석인지 여부에 따라 분기를 주어 구현한다.

 

n = 1 의 경우 경우의 수는 한가지이므로 dp[1] = 1, dp[2] 에서의 점화식이 성립하기 위해 dp[0] = 1로 초기화 후, 

위의 과정을 거쳐 좌석에 앉는 서로 다른 방법의 가짓수 dp[n] 을 정답으로써 출력한다.

 

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < m; i++)
            set.add(Integer.parseInt(br.readLine()));

        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            if (set.contains(i) || set.contains(i - 1))
                dp[i] = dp[i - 1];
            else
                dp[i] = dp[i - 1] + dp[i - 2];
        }

        bw.write(String.valueOf(dp[n]));
        bw.flush();
    }

}