[백준2302] 극장 좌석 - 자바(JAVA)

1. 문제

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

2302번: 극장 좌석

 

2. 풀이

제가 짠 코드의 알고리즘은

• `isVIP`라는 boolean 배열을 두어서 VIP좌석 표시하였습니다.
• `isVIP`를 탐색하다가 VIP좌석이 아닐때 count를 세고 VIP좌석을 발견했을 때 `dp[count]`를 결과값에 곱해주는 것입니다. 그래서 구현 편리성을 위해서 배열의 마지막 좌석 뒤(N+1)에 임의로 true로 하였습니다.
• `dp[n]`은 (VIP아닌)연속된 좌석이 n개 있을 때 앉을 수 있는 서로 다른 경우의 수 입니다.
• `dp[n]`은 `dp[n-1]+dp[n-2]`로 계산할 수 있습니다.
• 정답은 VIP좌석을 기준으로 양옆 연속된 좌석을 앉을 수 있는 경우의 수를 서로 곱해주면 정답이 됩니다.

저 같은 경우에는 메모장에 시뮬레이션을 해보면서 규칙을 찾을 수 있었습니다!

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ2302 {

	static int N, M, result = 0, pos;
	static boolean[] isVIP;
	static int dp[];

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		isVIP = new boolean[N + 2];

		dp = new int[N + 2];

		// 1. isVIP에 VIP 좌석은 true로 입력
		for (int i = 0; i < M; i++) {
			int input = Integer.parseInt(br.readLine());
			isVIP[input] = true;
		}
		// 마지막 좌석 바로 뒤에 임의로 VIP 좌석을 두었음(구현 편리성)
		isVIP[N+1]=true;

		int cnt = 0;
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		pos = 2;
		result = 1;

		for (int i = 1; i < N + 2; i++) {
			if (isVIP[i]) { // VIP 좌석일 때
				if (dp[cnt] == 0) { // dp값이 채워져있지 않을 때
					fill_dp(cnt); // 필요한 만큼 dp를 채운다
				}
				result *= dp[cnt];
				cnt = 0;
			} else { // VIP 좌석아닐 때
				cnt++;
			}
		}

		System.out.println(result);

	}

	public static void fill_dp(int last) {
		if (last < 3)
			return;
		for (int i = pos; i <= last; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		pos = last + 1;
	}

}