[백준 - 2302번] 극장 좌석 - 자바(JAVA) 정리 & 1일 1DP - 8일차

2302번: 극장 좌석

어떤식으로 풀었는지?

이번 문제 역시 DP문제이다. 

핵심은 결국에 고정된 VIP석을 제외한 나머지 가짓수에 대해서 곱으로 전체 경우를 구한다는 것.

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

 

완벽하게 이문제를 풀지를 못했고, 이분의 블로그를 많이 참고해서 풀었다

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

[백준] 2302 - 극장 좌석

 

/** 2020. 2. 26. 오후 2:38:27
 * @author ventulus95
 */
package codeBaekJoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class No2302_TheaterSeat {
	
	static int dp[] = new int [41];
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		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 ans = 1;
		int start =0; 
		int stop =0;
		for(int i=0; i<n; i++){
			stop = Integer.parseInt(br.readLine());
			ans *= dp[stop-start-1];
			start = stop;
		}
		ans *= dp[T-stop];
		System.out.println(ans);
	}
 
}