백준 - 극장 좌석 (2302) : JAVA

문제 유형
dp

풀이 방법 도출
문제의 조건은 다음과 같습니다.

1. 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다.
2. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.
3. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.
4. 그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.
5. 오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오. 

이 문제는 dp를 통해서 해결할 수 있습니다.

1. 연속된 1명이 자리를 앉을 수 있는 경우의 수는 1개
2. 연속된 2명이 자리를 앉을 수 있는 경우의 수는 2개

여기까지는 자명합니다.

연속된 3명이 자리를 앉을 수 있는 경우의 수는 3개입니다.

작은 문제로 큰 문제를 해결할 수 있는데 방법은 다음과 같습니다.

1. 연속된 3명 뒤에 1명이 추가된다.
2. 추가된 1명은 왼쪽에 있는 사람과 자리를 변경할 수 있다.
	a. 자리를 변경하지 않은 나머지 2명이 자리를 바꿀 수 있는 경우의 수는 2이다.
3. 추가된 1명이 왼쪽에 있는 사람과 자리를 변경하지 않는다면, 연속된 3명이 자리를 앉는 경우의 수 3이다.

정리하면

arr[i] = arr[i-1] + arr[i-2]

위와 같은 점화식을 만들 수 있습니다.
arr[i-1]은 자리를 이동하지 않을때, arr[i-2]는 자리를 바꿀 때의 경우의 수 입니다.

시간 복잡도
O(N)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		
		int m = Integer.parseInt(st.nextToken());
		
		
		int[] arr = new int[n+1];
		
		arr[0] = 1;
		arr[1] = 1;
		
		for (int i=2; i<=n; i++) {
			arr[i] = arr[i-1] + arr[i-2];
		}
		
		int prev = 0;
		int answer = 1;
		
		for (int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			
			
			answer *= arr[num - prev - 1];
		
			prev = num;
		}
		
		answer *= arr[n - prev];
		
		System.out.println(answer);
		

		
	}

	
}