[JAVA] 백준 2302번 : 극장 좌석

 

---

 

• 생각

첫번째 고정된 VIP석을 제외한 나머지 가짓수에 대해서 곱으로 전체 경우를 구한다는 것

두번째는 Vip좌석을 통해서 남겨진 좌석을 지정된 방법으로 섞었을때 가능한 경우의 수 찾는 것

 

잘 이해되지 않으면 참고하면 좋을 것 같다.

http://blog.naver.com/occidere/220854811310

[백준] 2302 - 극장 좌석

 

• 코드

정답 코드 : 점화식을 통해 구현한 코드이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int T, answer;
	static int[] dp;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		T = Integer.parseInt(br.readLine());
		answer = 1;
		dp = new int[41];
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= T; i++)
			dp[i] = dp[i - 1] + dp[i - 2];

		int n = Integer.parseInt(br.readLine());
		int start = 0;
		int stop = 0;
		for (int i = 0; i < n; i++) {
			stop = Integer.parseInt(br.readLine());
			answer *= dp[stop - start - 1];
			start = stop;
		}
		
		answer *= dp[T-stop];
		System.out.println(answer);
	}
}