[백준 / 실버1] 2302 극장 좌석 (Java)

문제 보기

사용한 것

• 점화식을 세워 문제를 해결하기 위한 bottom-up

풀이 방법

• VIP회원은 좌석이 고정이므로 확인을 위해 set에 넣어준다.
• 한명뿐이면 경우의 수가 1개이므로 dp의 1번째 인덱스에 1을 넣어주고 점화식을 세우기 위하여 0번째 인덱스에도 1을 넣어준다.
  
  
• for문에서 현재 인덱스나 이전 인덱스가 VIP석이면 섞어 앉을 수 없으므로 dp[i] = dp[i - 1]이다.
• 이외의 경우는 섞어 앉을 수 있고 점화식을 다음과 같이 도출한다. (바로 옆자리만 가능하기에 연속 2번 섞을 수 없음을 이용)
  • 이번 순번에 섞지 않음 : dp[i - 1]
  • 이번 순번에 섞어 앉음 : dp[i - 2]
  • 따라서 dp[i] = dp[i - 1] + dp[i - 2]

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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] = 1;
        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];
            }
        }

        System.out.println(dp[n]);
    }
}